Tiểu luận Đường đi ngắn nhất và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG
---v---
TIỂU LUẬN
TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG
Giáo viên hướng dẫn: PGS.TSKH.Trần Quốc Chiến Học viên thực hiện:	1.Vũ Văn Khiên
( nhóm 2)	2.Mai Quốc Toản 3.Nguyễn Hoàng Vi 4.Phan Thành Nhất 5.Lưu Thế Vinh
Lớp: Phương pháp Toán Sơ Cấp
Khoá: 2009 – 2011
Kon Tum, tháng 3 năm 2010.
MỤC LỤC
Lời nói đầu...Trang 01 Phần nội dung...............................................................................................Trang 02
I.	Cơ sở lý thuyết.Trang 02
II. Bài toán đường đi ngắn nhất và ứng dụng .Trang 05 Kết luận....Trang 25 Tài liệu tham khảo........Trang 26
LỜI NÓI ĐẦU
Lý thuyết đồ thị là ngành học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó đã được nhà toán học Thụy sĩ vĩ đại Leonhard Euler đưa ra từ thế kỷ 18.
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh vực khoa học, kỹ thuật, kinh tế, xã hội,...
Môn lý thuyết đồ thị là môn học hấp dẫn, mang tính thực tế cao. Những vấn đề trong môn học như: các bài toán về đường đi, cây, mạng và các bài toán tô màu đã và đang được nhiều người quan tâm, nghiên cứu. Bài toán tìm đường đi ngắn nhất là bài toán quan trọng trong Lý thuyết đồ thị, nó được áp dụng để giải quyết rất nhiều bài toán trong thực tế như điều khiển tối ưu, giao thông vận tải, mạng viễn thông ...
. Vì vậy, việc nghiên cứu nó là hết sức cần thiết vì nó có thể giải quyết được nhiều vấn đề khó khăn, phức tạp nảy sinh từ thực tế cuộc sống.
Vì lí do đó, nhóm chúng em (nhóm 2) chọn đề tài: ''Đường đi ngắn nhất và ứng dụng'' để viết bài tiểu luận này.
PHẦN NỘI DUNG
CƠ SỞ LÝ THUYẾT
Đồ thị vô hướng
Định nghĩa: Đồ thị vô hướng G = (V, E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnh e	E được liên kết với một cặp đỉnh v, w (không kể thứ tự).
v	w
Ví dụ:	e
Đồ thị có hướng.
Định nghĩa: Đồ thị có hướng G = (V , E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung . Mỗi cung được liên kết với một cặp đỉnh (v, w) có thứ tự.
v	w
e
Ví dụ:
Đường đi, chu trình , tính liên thông
Cho đồ thị G=(V,E).
Dãy m từ đỉnh v đến w là dãy các đỉnh và cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dãy m gọi là độ dài của dãy m .
Dãy m từ đỉnh v đến đỉnh w độ dài n được biểu diễn như sau
m = (v,e1, v1,e2 , v2 ,..., vn-1,en , w)
trong đó vi(i=1,2,n-1) là các đỉnh trên dãy và ei(i=1,2,n) là các cạnh trên dãy liên thông thuộc đỉnh kề trước và sau nó. Các đỉnh và cạnh trên có thể lặp lại.
Đường đi từ đỉnh v đến w là dãy từ đỉnh v đến w, trong đó các cạnh không lặp
lại.

Đường đi sơ cấp : là đường đi không đi qua một đỉnh quá một lần
Vòng là dãy có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau
Chu trình sơ cấp : là chu trình không đi qua một đỉnh quá một lần.
Dãy có hướng : trong đồ thị có hướng là dãy các đỉnh và cung nối tiếp nhau (e1,e2,,en) thỏa mãn đỉnh cuối của cung ei là đỉnh đầu của cung ei+1,
i=1,..n-1.
Đường đi có hướng trong đồ thị có hướng là dãy có hướng, trong đó các
cung không lặp lại.
Đường đi có hướng sơ cấp là đường đi có hướng không đi qua một đỉnh quá một lần.
Vòng có hướng là dãy có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng sơ cấp là chu trình có hướng không đi qua một đỉnh quá một lần .
Đồ thị có hướng gọi là liên thông, nếu mọi cặp đỉnh của nó đều có đường đi
nối chúng với nhau.
Đồ thị có hướng gọi là liên thông mạnh, nếu mọi cặp đỉnh của nó đều có
đường đi có hướng nối chúng với nhau.
Đồ thị có hướng gọi là liên thông yếu, nếu đồ thị lót (vô hướng) của nó liên thông.
Đồ thị có hướng gọi là bán liên thông, nếu với mọi cặp đỉnh (u,v) bao giờ cũng tồn tại đường đi có hướng từ u đến v hoặc từ v đến u.
Định lí 1:
Trong đồ thị vô hướng mỗi dãy từ đỉnh v đến w chứa đường đi sơ cấp từ v đến w
Trong đồ thị có hướng mỗi dãy có hướng từ đỉnh v đến w chứa đường đi có hướng sơ cấp từ v đến w.
Định lí 2: Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ.
Trọng đồ (có hướng) là đồ thị (có hướng) mà mỗi cạnh (cung) của nó được gán một số.
Trọng đồ được biểu diễn bởi G=(V,E,w), trong đó V là các đỉnh ,E là tập các
cạnh(cung), và w : E ® R
với mọi e Î E.
là hàm số trên E, w(e) là trọng số của cạnh(cung) e
Trong trọng đồ độ dài trọng số của đường đi m là tổng các trọng số trên đường đi đó.
BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG
Phát biểu bài toán
Cho đồ thị có trọng số G=(V,E). Kí hiệu w(i,j) là trọng số của các cạnh (i,j). Độ dài
đường đi m = v0 ® v1 ® v2 ® ... ® vn-1 ® vn
là tổng các trọng số

n
L(m ) = åw(vi-1,vi )
i=1
Cho hai đỉnh a,z của đồ thị. Bài toán đặt ra là tìm đường đi ngắn nhất từ a đến z.
Thuật toán Dijkstra
Thật toán tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đó đồ thị liên thông có trọng số. trọng số cạnh (i,j) là w(i,j)>0 và đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải L(z) chính là chiều dài ngắn nhất từ a đến z.
Đầu vào: đồ thị liên thông G=(V,E) có trọng số w(i,j)>0 với mọi cạnh (i,j), đỉnh a và z
Đầu ra :L(z) chiều dài đường đi ngắn nhất từ a đến z và đường đi ngắn nhất.
Phương pháp:
Gán L(a):=0, với mọi x khác a gán L(a)= ¥ . Kí hiệu T:=V
Chọn v ÎT
T:=T-{v}
sao cho L(v) có giá trị nhỏ nhất. Đặt
Nếu z ÏT , kết thúc, L(z) là chiều dài đường đi ngắn nhất từ a đến z. Từ z lần ngược theo đỉnh được ghi nhớ ta có đường đi ngắn nhất. Ngược lại sang bước (4)
Với mỗi x ÎT
kề v gán
L(x):=min{L(x),L(v)+w(v,x)}
Nếu L(x) thay đổi thi ghi nhớ đỉnh v cạnh x để sau này xây dựng đường đi
ngắn nhất.	Quay về bước (2)
-Định lí : Thuật toán Dijkstra là đúng.
Chứng minh: xem [1]
Ví dụ1: Cho các tỉnh a,b,c,d,e,f,g,z có vị trí như sơ đồ sau. Biết rằng giữa các tỉnh có đoạn đường nối với nhau có độ dài như hình vẽ. Tìm đường đi ngắn nhất từ tỉnh
a đến tỉnh z
2	b	2	c
4
4
2	3	1
z
a	d	e
1	3	7
f	5	g	6
- Ta thực hiện bước 1:
Đặt T:={a,b,c,d,e,f,g,z}
Giải:
Và L(a):=0, L(b)=L(c)=L(d)=L(e)=L(f)=L(g)=L(z):=∞
Các tham số trên được biểu diễn trên đồ thị như sau
4
)
4
2 b(∞ )	2

c(∞ )
a(0)
2
d (∞ 1	3
f(∞ )	5
3	1
e(∞) 7
g(∞)6

z(∞ )
Các số trong ngoặc là L(x), x Î T.
-Thực hiện bước 2:
L(a)=min{L(x)| x Î T}=0
Suy ra T:=T-{a}={a,b,c,d,e,f,g,z}
Thực hiện bước 3: vì z Î T, chuyển sang bước 4:
Thực hiện bước 4:
Đỉnh b và f kề đỉnh a. Ta có L(b)=min{L(b),L(a)+2}=2
L(f)= min{L(f),L(a)+1}=1
Các đỉnh không thay đổi. Đồ thị có các nhãn như sau
4
)
4
2 b(2 )a 2

c(∞ )
a(0)
2
d (∞ 1	3
f(1 )a 5
3	1
e(∞) 7
g(∞)6

z(∞ )
Chú ý: Các chữ cái bên phải ở mỗi đỉnh là nhãn đỉnh đạt giá trị nhỏ nhất ở các biểu thức tính min.
- Ta thực hiện bước 2:
L(f)=min{L(x)| x Î T}=1
Suy ra
T=T-{f}={b,c,d,e,g,z}
- Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh d và g kề đỉnh f. Ta có L(d)=min{L(d), L(f)+2}=min{ ∞ , 1+3}=4
L(g)=min{L(g), L(f)+5}=min{ ∞ , 1+5}=6
4
)f
4
2
b(2 )a
2
c(∞ )
2
3
e(∞)
1
1
d (4
3
7	6
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)

f(1 )a 5

g(6)f
z(∞ )
- Ta thực hiện bước 2:
Suy ra
L(b)=min{L(x)| x Î T}=2 T=T-{b}={c,d,e,g,z}
- Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh c,d và e kề đỉnh b. Ta có L(c)=min{L(c), L(b)+2}=min{ ∞ , 2+2}=4
L(d)=min{L(d), L(b)+2}=min{ 4 , 2+2}=4
L(e)=min{L(e), L(b)+4}=min{ ∞ , 2+4}=6
4
)f
4
2
b(2 )a
2
1
d (4
3
2
c(4 )b
e(6)b
3
1
7	6
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)

f(1 )a 5

g(6)f
z(∞ )
Ta thực hiện bước 2:
Suy ra
L(c)=min{L(x)| x Î T}=4 T=T-{c}={d,e,g,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh e và z kề đỉnh c. Ta có L(e)=min{L(e), L(c)+3}=min{ 6 , 4+3}=6
L(z)=min{L(z), L(c)+1}=min{ ∞ , 4+1}=5
4
)f
4
2
b(2 )a
2
1
d (4
3
2
c(4 )b
e(6)b
3
1
7	6
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)

f(1 )a 5

g(6)f
z(5 )c
Ta thực hiện bước 2:
Suy ra
L(d)=min{L(x)| x Î T}=4 T=T-{d}={e,g,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh e kề đỉnh d. Ta có
L(e)=min{L(e), L(d)+4}=min{ 6 , 4+4}=6
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
4
)f
4
2
b(2 )a
2
1
d (4
3
2
c(4 )b
e(6)b
3
1
7	6
a(0)
- Ta thực hiện bước 2:

f(1 )a 5

g(6)f
z(5 )c
Suy ra
L(z)=min{L(x)| x Î T}=5
T=T-{z}={e,g}
- Ta thực hiện bước 3: z Ï T, kết thúc.
L(z)=5 là độ dài đường đi ngắn nhất từ a đến z.
Từ z ta đi ngược lại các đỉnh đã được ghi nhớ z ® c ® b ® a . Ta suy ra đường đi ngắn nhất là a ® b ® c ® z .
Ví dụ2: Tìm đường đi ngắn nhất từ tỉnh a đến tỉnh z trong đồ thị sau:
a
Giải:
z
3
1
4
b
5
c
5
d
7
2
2
3
4
e	6	f	5	g
- Ta thực hiện bước 1:
Đặt T:={a,b,c,d,e,f,g,z}
Và L(a):=0, L(b)=L(c)=L(d)=L(e)=L(f)=L(g)=L(z):=∞
Các tham số trên được biểu diễn trên đồ thị như sau
a(0)
4	b(∞ )	c(∞ )
5
3
6
5
1
5
2
3
e(∞ )	f(∞ )
d(∞ )
7
2
4
g(∞ )

z(∞ )
Các số trong ngoặc là L(x), x Î T.
-Thực hiện bước 2:
L(a)=min{L(x)| x Î T}=0
Suy ra T:=T-{a}={a,b,c,d,e,f,g,z}
Thực hiện bước 3: vì z Î T, chuyển sang bước 4:
Thực hiện bước 4:
Đỉnh b và f kề đỉnh a. Ta có L(b)=min{L(b),L(a)+2}=2
L(f)= min{L(f),L(a)+1}=1
Các đỉnh không thay đổi. Đồ thị có các nhãn như sau
a(0)
4	b(4 )a	c(∞ ) 2
5
3
6
5
1
5
3
e(3 )a	f(∞ )
d(∞ )
7
2
4
g(∞ )

z(∞ )
Chú ý: Các chữ cái bên phải ở mỗi đỉnh là nhãn đỉnh đạt giá trị nhỏ nhất ở các biểu thức tính min.
Ta thực hiện bước 2:
L(e)=min{L(x)| x Î T}=3
Suy ra
T=T-{e}={b,c,d,f,g,z}
- Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh b,cvà f kề đỉnh e. Ta có
L(b)=min{L(b), L(e)+3}=min{ 4 , 2+3}=4
L(c)=min{L(c), L(e)+3}=min{ ∞ , 3+3}=6
L(f)=min{L(f), L(e)+3}=min{ ∞ , 6+3}=9
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)
4	b(4 )a	c(6 )e 2
5
3
6
5
1
5
3
e(3 )a	f(9 )e
d(∞ )
7
2
4
g(∞ )

z(∞ )
Ta thực hiện bước 2:
Suy ra
L(b)=min{L(x)| x Î T}=4 T=T-{b}={c,d,f,g,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh c kề đỉnh b. Ta có
L(c)=min{L(c), L(b)+5}=min{ 6 , 4+5}=6
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)
4	b(4 )a	c(6 )e 2
5
3
6
5
1
5
3
e(3 )a	f(9 )e
d(∞ )
7
2
4
g(∞ )

z(∞ )
Ta thực hiện bước 2:
Suy ra
L(c)=min{L(x)| x Î T}=6 T=T-{c}={d,f,g,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh f và d kề đỉnh c. Ta có
L(f)=min{L(f), L(c)+1}=min{ 9 , 6+1}=7
L(d)=min{L(d), L(c)+5}=min{ ∞ , 6+5}=11
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)
4	b(4 )a	c(6 )e 2
5
3
6
5
1
5
3
e(3 )a	f(7)c
d(11 )
7
2
4
g(∞ )

z(∞ )
Ta thực hiện bước 2:
Suy ra
L(f)=min{L(x)| x Î T}=7 T=T-{f}={d,g,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh g kề đỉnh f. Ta có
L(g)=min{L(g), L(f)+5}=min{ ∞ , 7+5}=12
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)
4	b(4 )a	c(6 )e 2
5
3
6
5
1
5
3
e(3 )a	f(7)c
d(11 )
7
2
4
g(12)

z(∞ )
Ta thực hiện bước 2:
Suy ra
L(g)=min{L(x)| x Î T}=12 T=T-{g}={d,z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
Đỉnh d và z kề đỉnh g. Ta có
L(d)=min{L(d), L(g)+2}=min{ 11 , 12+2}=11
L(z)=min{L(z), L(g)+4}=min{ ∞ , 12+4}=16
5
3
6
5
1
5
4
b(4 )a
c(6 )e
2
d(11 )
7
2
3
4
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)

e(3 )a	f(7)c

g(12)
z(16 )g
Ta thực hiện bước 2:
Suy ra
L(d)=min{L(x)| x Î T}=11 T=T-{d}={z}
Ta thực hiện bước 3: z Î T, chuyển sang bước 4
- Ta thực hiện bước 4:
L(z)=min{L(z), L(d)+7}=min{ 16	, 11+7}=16
5
3
6
5
1
5
4
b(4 )a
c(6 )e
2
d(11 )
7
2
3
4
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
a(0)

e(3 )a	f(7)c

g(12)
z(16 )g
- Ta thực hiện bước 3: z Ï T, kết thúc.
L(z)=16 là độ dài đường đi ngắn nhất từ a đến z.
Từ z ta đi ngược lại các đỉnh đã được ghi nhớ z ® g ® f

® c ® e ® a . Ta suy
ra đường đi ngắn nhất là a ® e ® c ® f ® g ® z .
Phương pháp lập bảng ghi nhãn
Ta lập bảng tính toán các nhãn gồm các cột ứng với các đỉnh, và các hàng ứng với các lần tính nhãn ở bước (4). Các nhãn gạch dưới ứng với nhãn nhỏ nhất ở bước (2), và đỉnh bị loại ghi bên phải. Sau khi đỉnh z bị loại, từ z lần nguợc về đỉnh a theo nhãn ghi trên bảng. Các đỉnh trên đường đi được gạch dưới ( trên cột các đỉnh loại). Cuối cùng theo thứ tự ngược lại ta nhận được đường đi ngắn nhất.
Sau đây là bảng tính toán nhãn của ví dụ1 trên
1
2
3
4
5
6
a
0
b
c
d
e
f
g
z
2(a)
2
1(a)
4(b)
4(f)
4
4
6(b)
6
6
6(f)
6
6
6
5(c)
5
a f b c d
z
Ta suy ra đường đi ngắn nhất là

a ® b ® c ® z
Sau đây là bảng tính toán nhãn của ví dụ 2 trên
1
2
3
4
5
6
7
a
0
b
c
d
e
f
g
z
4(a)
4
3(a)
6(e)
6
11(c)
11
11
9(e)
9(c)
7(c)
12(f)
12
18(d)
16(g)
a e b c f d
 g
z
Ta suy ra đường đi ngắn nhất là

z ® g ® f

® c ® e ® a
Định lí : Giả sử G là đồ thị liên thông có trọng số và có n đỉnh. Gọi f(n) là số lần thuật toán Dijkstra khảo sát một cạnh của G trong trường hợp xấu nhất. Khi đó ta có
f(n) = O(n2)
Chứng minh : xem [1]
Thuật toán Floyd
Thuật giải tìm độ dài đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng
liên thông có trọng số (không bắt buộc
³ 0 ).
+ Đầu vào. Đồ thị liên thông G = (V, E), V = {1, 2,..., n
mọi cung (i,j).
} , có trọng số w(i,j) với
+Đầu ra. Ma trận D= [d (i, j)] trong đó d(i,j) là chiều dài đường đi ngắn nhất từ i
đến j với mọi cặp (i,j).
+Phương pháp.
Bước khởi tạo: Kí hiệu Do là ma trận xuất phát
D0=[d0 (i, j)]
Trong đó do9i,j) = w(i,j) nếu tồn tại cung (i,j) và do(i,j) = + ¥ nếu không tồn tại
cung (i,j) đặc biệt nếu không có khuyên tại i thì do(i,i)= + ¥ ).
Gán k:=0
Kiểm tra kết thúc: Nếu k=n , kết thúc. D=Dn là ma trận độ dài đường đi ngắn nhất. Ngược lại tăng k lên 1 đơn vị (k:=k+1) và sang (3).
Tính ma trận Dk theo Dk-1:
Với mọi cặp (i,j), i=1..n, j=1..n thực hiện:
Nếu dk-1(i,j) > dk-1(i,k) + dk-1(k,j) thì đặt
dk(i,j) := dk-1(i,k) + dk-1(k,j)
Ngược lại đặt
Quay lại bước (2).

dk(i,j):=dk-1(i,j)
* Định lí: Thuật toán Floyd là đúng.
Chứng minh: xem [1]
*Hệ quả
Nếu ma trận kết quả của thuật toán Floyd có phần tử hữu hạn trên đường chéo i=i thì đồ thị đó chứa chu trình.
Nếu ma trận kết quả chứa phần tử + ¥ ngoài đường chéo i=i thì đồ thị không
liên thông mạnh.
+ Ví dụ: Xét đồ thị sau
1	7	2	4	3
2
2	2	4	1	1	3
4	5	6
Áp dụng thuật toán Floyd ta có:
Đỉnh
1
2
3
4
5
6
1
7
2
2
4
1
3
3
4
4
5
2
2
6
1
Ma trận khoảng cách xuất phát Do là ( các ô trống là ¥ ):
Do =
Từ ma trận do, theo thuật toán, ta xây dựng các ma trận tiếp theo như sau( các ô
gạch dưới có giá trị thay đổi)
Đỉnh
1
2
3
4
5
6
1
7
2
2
4
1
3
3
4
4
5
2
9
2
4
6
1
D1 =
Đỉnh
1
2
3
4
5
6
1
7
11
2
8
2
4
1
3
3
4
4
8
5
5
2
9
2
4
10
6
1
5
2
D2 =
Đỉnh
1
2
3
4
5
6
1
7
11
2
8
14
2
4
1
7
3
3
4
4
8
5
11
5
2
9
2
4
10
5
6
1
5
2
8
D3 =
Đỉnh
1
2
3
4
5
6
1
6
10
2
7
13
2
4
1
7
3
3
4
4
8
5
11
5
2
8
2
4
9
5
6
1
5
2
8
D4 =
Đỉnh
1
2
3
4
5
6
1
9
6
9
2
7
12
2
3
9
3
5
1
6
3
3
4
7
4
7
9
5
10
5
2
8
2
4
9
5
6
4
1
4
6
2
7
D5 =
Đỉnh
1
2
3
4
5
6
1
9
6
9
2
7
12
2
3
7
3
5
1
6
3
7
4
7
9
5
3
4
7
4
7
9
5
10
5
2
6
2
4
7
5
6
4
1
4
6
2
7
D =D6 =
Cuối cùng, D là ma trận khoảng cách ngắn nhất giữa các đỉnh. Theo hệ quả ta thấy
đồ thị liên thông và chứa chu trình.
Thuật toán Floyd –Warshall
Thuật giải tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng liên thông có trọng số.
+Đầu vào. Đồ thị liên thông G=(V,E), V= {1, 2,..., n}, có trọng số với mọi cung (i,j).
+Đầu ra. Ma trận D =[d (i, j)], trong đó d(i,j) là chiều dài đường đi ngắn nhất từ i
đến j với mọi cặp (i,j).
Ma trận P= [ p(i, j)] dùng để xác định đường đi ngắn nhất.
+Phương pháp.
Bước khởi tạo: Kí hiệu D0 là ma trận xuất phát D0= [d (i, j)]
trong đó d0(i,j) =w(i,j) nếu tồn tại cung (i,j) và d0(i,j) = + ¥ nếu không tồn tại cung
(i,j) ( đặc biệt nếu không có khuyên tại i thì d0(i,i) = + ¥ ).
P0= [ p0 (i, j)]
trong đó p0(i,j) = j nếu có cung từ i đến j và p0(i,j) không xác định nếu không có cung từ i đến j.
Gán k:=0.
Kiểm tra kết thúc:
Nếu k=n, kết thúc. D= Dn là ma trận độ dài đường đi ngắn nhất, P = Pn.
Ngược lại tăng k lên 1 đơn vị (k:=k+1) và sang (3).
Tính ma trận Dk và Pk theo Dk-1 và Pk-1: Với mọi cặp (i,j), i= 1..n, j=1..n thực hiện: Nếu dk-1(i,j) > dk-1(i,k) + dk-1(k,j) thì đặt
Dk(i,j):= dk-1(i,k) + dk-1(k,j)
và
pk(i,j):=pk-1(i,k)
ngược lại đặt
dk(i,j):= dk-1(i,j)
và
pk(i,j):= pk-1(i,j)
Quay lại bước (2).
Phương pháp xác định đường đi ngắn nhất từ đỉnh i đến đỉnh j: Đường đi ngắn nhất từ i đến j gồm dãy các đỉnh
I , i1, i2, i3,, ik, ik+1,, im, j
thỏa mãn
i1= p(i,j), i2 =p(i1, j),  , ik+1 = p(ik,j),  , p(im,j) =j
6
1
7
4
7
a
5
11
+Ví dụ1. Xét đồ thị
b	d
c
Áp dụng giải thuật Floyd mở rộng ta nhận được các ma trận sau:
Các ma trận xuất phát:
a
7
5
a
b
c
D0 =
b
7
6
P0 =
b
c
d
c
11
c
d
d
4
1
d
a
b
Các ma trận cập nhật qua đỉnh a:( các giá trị mới được gạch dưới) Vì (d,c) > (d,a) + (a,c) thì đặt	(d,c):= (d,a) + (a,c)
-
a	b	c	d	a	b	c	d
-
a
b
c
d
a
b
c
d
a
7
5
a
b
c
D1 =
b
7
6
P1 =
b
c
d
c
11
c
d
d
4
1
9
d
a
b
a
-	Các ma trận cập nhật qua đỉnh b:
Vì (a ,d)>(a,b)+(b,d) nên đặt (a ,d):=(a,b)+(b,d); Vì (d ,c)>(d,b)+(b,c) nên đặt
(d ,c):=(d,b)+(b,c); (d,d)>(d,b)+(b,d) nên đặt (d,d):=(d,b)+(b,d)
a
b
c
d
a
b
c
a
7
5
13
a
b
c
b
D2 =
b
7
6
P2 =
b
c
d
c
11
c
d
d
4
1
8
7
d
a
b
b
b
22
d
Các ma trận cập nhật qua đỉnh c:
a
b
c
d
a
b
c
d
a
7
5
13
a
b
c
b
D3 =
b
7
6
P3 =
b
c
d
c
11
c
d
d
4
1
8
7
d
a
b
b
b
(không thay đổi).
-	Tương tự ta có các ma trận cập nhật qua đỉnh d:
a
b
c
d
a
b
c
d
a
17
7
5
13
a
b
b
c
b
D=D4 =
b
10
7
7
6
P=P4 =
b
d
d
c
d
c
15
12
19
11
c
d
d
d
d
d
4
1
8
7
d
a
b
b
b
Cuối cùng, ta có ma trận khoảng cách ngắn nhất giữa các đỉnh D=D4. Ta thấy
đồ thị liên thông và chứa chu trình.
Sử dụng ma trận P=P4, ta có thể tìm đườn đi ngắn nhất giữa các đỉnh. Chẳng hạn, để tìm đường đi từ đỉnh a đến đỉnh d ta làm như sau:
Đặt
i1 := P(a,d) = b; i2 : = P(b,d) = d
Từ đó ta nhận được đường đi ngắn nhất từ d đến c: a ® b ® d với độ dài là 8
Ví dụ 2: Dùng giải thuật Floyd tìm đường đi ngắn nhất giữa các đỉnh trong đồ thị
có hướng có trọng số sau	3
B
4
C
8
D
3
3
3
A
7
1
E
1
1
3
5
5
e
G
F
12
Áp dụng giải thuật Floyd mở rộng ta nhận được các ma trận sau:
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
1
A
B
4
3
B
D0=	C
8
3
P0=
C
D
3
3
D
E
12
E
F
1
F
G
1
7
5
G
-	Các ma trận xuất phát:
B
C
F
D
F
A
E
G
D
C
D
F
- Các ma trận cập nhật qua đỉnh A: (các giá trị mới được gạch dưới, tô màu
1
4
3
8
3
3
4
5
3
12
1
1
7
5
B
C
F
D
F
A
A
A
E
G
D
C
D
F
đỏ)	A	B	C	D	E	F	G A
B
D1= C D E F
G

A B
P1= C D E F G
A	B	C	D	E	F	G
B
B
B
C
F
D
F
A
A
A
E
B
G
D
C
D
F
B
B
C
B
C
F
D
F
A
A
A
C
E
B
G
D
C
D
C
- Các ma trận cập nhật qua đỉnh B: (các giá trị mới được gạch dưới, to màu)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
1
5
4
A
B
4
3
B
D2=	C
8
3
P2=
C
D
3
4
5
3
7
D
E
12
E
F
1
F
G
1
7
5
G
- Các ma trận cập nhật qua đỉnh C: (các giá trị mới được gạch dưới, tô màu)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
1
5
13
4
A
B
12
3
B
D3=	C
8
3
P3=
C
D
3
4
5
13
3
7
D
E
12
E
F
1
F
G
1
7
4
G
D
B
B
C
D
B
D
D
D
C
D
F
D
F
A
A
A
C
E
B
G
D
D
D
D
D
D
D
D
C
D
D
C
- Các ma trận cập nhật qua đỉnh D: (các giá trị mới được gạch dưới,tô màu)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
16
1
5
13
16
4
A
B
15
16
17
12
15
3
B
D4=	C
8
3
P4=
C
D
3
4
5
13
3
7
D
E
12
E
F
4
5
6
1
4
11
F
G
10
11
1
7
10
4
G
16
1
5
13
16
4
28
15
16
17
12
15
3
27
8
3
3
4
5
13
3
7
15
12
4
5
6
1
4
11
16
10
11
1
7
10
4
16
D
B
B
C
D
B
E
D
D
D
C
D
F
E
D
F
A
A
A
C
E
B
E
G
D
D
D
D
D
D
E
D
D
C
D
D
C
E
- Các ma trận cập nhật qua đỉnh E: (các giá trị mới được gạch dưới, tô màu)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
A
B
B
D5=	C
P5=
C
D
D
E
E
F
F
G
G
F
B
B
F
F
B
F
F
F
D
F
F
F
F
F
F
F
F
F
F
F
A
A
A
F
E
B
E
G
D
D
D
D
D
D
E
F
F
C
F
F
C
E
- Các ma trận cập nhật qua đỉnh F: (các giá trị mới được gạch dưới)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
8
1
5
5
8
4
20
A
B
7
8
9
4
7
3
19
B
D6=	C
7
8
9
4
7
3
19
P6=
C
D
3
4
5
8
3
7
15
D
E
12
E
F
4
5
6
1
4
11
16
F
G
8
9
1
5
8
4
16
G
- Các ma trận cập nhật qua đỉnh G: (các giá trị mới được gạch dưới)
A
B
C
D
E
F
G
A	B	C	D	E	F	G
A
A
B
B
D7=	C
P7=
C
D
D
E
E
F
F
G
G
8
1
5
5
8
4
20
7
8
9
4
7
3
19
7
8
9
4
7
3
19
3
4
5
8
3
7
15
20
21
13
17
20
16
12
4
5
6
1
4
11
16
8
9
1
5
8
4
16
F
B
B
F
F
B
F
F
F
D
F
F
F
F
F
F
F
F
F
F
F
A
A
A
F
E
B
E
G
G
G
G
G
G
G
D
D
D
D
D
D
E
F
F
C
F
F
C
E
Cuối cùng, ta có ma trận khoảng cách ngắn nhất giữa các đỉnh D=D7. Ta thấy đồ
thị liên thông và chứa chu trình.
Sử dụng ma trận P=P7, ta có thể tìm đườn đi ngắn nhất giữa các đỉnh. Chẳng hạn,
để tìm đường đi từ đỉnh C đến đỉnh B ta làm như sau: Đặt
i1 := P(C,B) = F; i2 : = P(F,B) = D,i3=p(D,B)=A,i4=P(A,B)=B
Từ đó ta nhận được đường đi ngắn nhất từ C đến B: C ® F ® D ® A ® B với
độ dài là 8
KẾT LUẬN
Bài toán tìm đường đi ngắn nhất là bài toán rất hay, nó khơi dậy khả năng toán học cho người học, đồng thời nó cũng kích thích được óc sáng tạo và tư duy định hướng cho người học.
Bài toán này đã cuốn hút được sự quan tâm của nhiều người bởi tính đa dạng và sự ứng dụng của nó. Do vậy, việc học tập, nghiên cứu chủ đề này là rất bổ ích vì nó có thể giải quyết được nhiều vấn đề nảy sinh từ thực tế cuộc sống.
Trong đề tài này, mặt dù nhóm em đã dành nhiều thời gian nghiên cứu, thảo luận, và được sự hướng dẫn chu đáo của Thầy PGS.TSKH.Trần Quốc Chiến nhưng do khả năng có hạn nên chắc chắn đề tài không tránh khỏi thiếu sót. Kính mong Thầy và các anh chị trong lớp góp ý, bổ sung, chỉnh sửa để đề tài được hoàn thiện hơn.
Thay mặt nhóm, em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn nhiệt tình, tận tụy của Thầy PGS.TSKH.Trần Quốc Chiến, cũng như sự động viên, khích lệ của tập thể lớp để nhóm em hoàn thành tốt đề tài này.
TÀI LIỆU THAM KHẢO
PGS.TSKH Trần Quốc Chiến, Giáo Trình Lý Thuyết Đồ Thị, Đà Nẵng _2005.
Hoàng Chúng, Graph, Nhà xuất bản Giáo Dục.
TSKH Vũ Đình Hoà, Một số kiến thức cơ sở về Graph hữu hạn, Nhà xuất bản Giáo Dục.
Từ Văn Mặc, Trần Thị Ái ( biên dịch ), Chìa khoá vàng Toán Học, Nhà xuất bản Đại Học Quốc Gia Hà Nội.