1
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

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.
2
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
3
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

gọi là độ dài của dãy
µ
.
Dãy
µ
từ đỉnh v đến đỉnh w độ dài n được biểu diễn như sau
1 1 2 2 1
( , , , , , , , ,w)
n n
v e v e v v e
µ
−
=
v w
e
v w
e
5
trong đó v
i
(i=1,2…,n-1) là các đỉnh trên dãy và e
i
(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.

6
• Định lí 1:
(i) 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
(ii) 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→
là hàm số trên E, w(e) là trọng số của cạnh(cung) e
với mọi e ∈ E.
Trong trọng đồ độ dài trọng số của đường đi
µ
là tổng các trọng số trên đường đi
đó.
7
II . BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG
1. 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
0 1 2 1

n n
v v v v v
µ
−

(3) 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)
(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)
b
c
a
f g
z
e
d
2
1
6
5
4
4
3
2
2
1
7
3

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

2
1
6
5
4
4
3
2
2
1
7
3
10
- 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
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
- Ta thực hiện bước 2:
L(c)=min{L(x)| x ∈ T}=4
Suy ra
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
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
b(2 )a

1
6
5
4
4
3
2
2
1
7
3
11
- Ta thực hiện bước 2:
L(d)=min{L(x)| x ∈ T}=4
Suy ra
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
- Ta thực hiện bước 2:
L(z)=min{L(x)| x ∈ T}=5
Suy ra
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

2
5
7
56
3
2
4
3
1
5
d
z
g
4
12
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
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
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:

5
6
3
2
4
3
1
5
d(∞ )
z(∞ )
g(∞ )
4
13
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
- Ta thực hiện bước 2:
L(b)=min{L(x)| x ∈ T}=4
Suy ra
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
- Ta thực hiện bước 2:
L(c)=min{L(x)| x ∈ T}=6
Suy ra
T=T-{c}={d,f,g,z}

2
4
3
1
5
d(∞ )
z(∞ )
g(∞ )
4
14
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
- Ta thực hiện bước 2:
L(f)=min{L(x)| x ∈ T}=7
Suy ra
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
- Ta thực hiện bước 2:
L(g)=min{L(x)| x ∈ T}=12
Suy ra
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ó
b(4 )a c(6 )e

5
d(11 )
z(∞ )
g(12)
4
15
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
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
- Ta thực hiện bước 2:
L(d)=min{L(x)| x ∈ T}=11
Suy ra
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
Các đỉnh không thay đổi. Đồ thị có nhãn như sau
- 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→ → → → →
.
b(4 )a c(6 )e
a(0)
e(3 )a f(7)c
2
5

4
16
3. 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
a b c d e f g z
1 0 a
2 2(a) 1(a) f
3 2 4(f) 6(f) b
4 4(b) 4 6(b) 6 c
5 4 6 6 5(c) d
6 6 6 5 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
a b c d e f g z
1 0 a
2 4(a) 3(a) e
3 4 6(e) 9(e) b
4 6 11(c) 9(c) c
5 11 7(c) f
6 11 12(f) d
7 12 18(d) g
16(g) z
Ta suy ra đường đi ngắn nhất là
z g f c e a→ → → → →

=
[ ]
0
( , )d i j
Trong đó d
o
9i,j) = w(i,j) nếu tồn tại cung (i,j) và d
o
(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ì d
o
(i,i)= +
∞
).
Gán k:=0
(2)Kiểm tra kết thúc: Nếu k=n , kết thúc. D=D
n
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).
(3) Tính ma trận D
k
theo D
k-1
:
Với mọi cặp (i,j), i=1 n, j=1 n thực hiện:
Nếu d
k-1
(i,j) > d

Ma trận khoảng cách xuất phát D
o
là ( các ô trống là
∞
):D
o
=
Đỉnh 1 2 3 4 5 6
1 7 2
2 4 1
3 3
4 4
5 2 2
6 1
Từ ma trận d
o
, 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)
D
1
=
Đỉnh 1 2 3 4 5 6
1 7 2
2 4 1
3 3
4 4
5 2 9 2 4

Đỉ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
D
4
=
Đỉ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
D
5
=
Đỉ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
D =D
6
=

là ma trận xuất phát
D
0
=
[ ]
( , )d i j
trong đó d
0
(i,j) =w(i,j) nếu tồn tại cung (i,j) và d
0
(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ì d
0
(i,i) = +
∞
).
P
0
=
[ ]
0
( , )p i j
trong đó p
0
(i,j) = j nếu có cung từ i đến j và p
0
(i,j) không xác định nếu không có
cung từ i đến j.

k-1
(k,j)
và
21
p
k
(i,j):=p
k-1
(i,k)
ngược lại đặt
d
k
(i,j):= d
k-1
(i,j)
và
p
k
(i,j):= p
k-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 , i
1
, i
2
, i
3

0
= abcdabcbcdcddab
D
1
= abcda75b76c11d419
P
1
= abcdabcbcdcddaba
c
6
d
a
11
1
4
7
7
5
b
22
- 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)
Các ma trận cập nhật qua đỉnh c:
(không thay đổi).
- Tương tự ta có các ma trận cập nhật qua đỉnh d:
Cuối cùng, ta có ma trận khoảng cách ngắn nhất giữa các đỉnh D=D
4
. Ta thấy
đồ thị liên thông và chứa chu trình.

2
: = 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
Á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:
- 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
đỏ)
ŠBCDEFGŠ1B43D
1
=C83D3453E12F1
G175
ŠBCDEFGŠBBCFP
1
=CDFDŠŠŠEEGFDG
CDF
ŠBCDEFGŠ1B43D
0
=C83D33E12F1
G175
ŠBCDEFGŠBBCFP
0
=CDFDŠEEGFDGCD
F
Š
B
C

FDGCDF
ŠBCDEFGŠ15134B123D
3
=C83D345
1337E12F1
G174
ŠBCDEFGŠBBCBBCFP
3
=CDFDŠŠŠCEB
EGFDGCDC
25
- 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)
- 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)
ŠBCDEFGŠ161513164B15161712153
D
4
=C83D3451337E12F4561411
G101117104
ŠBCDEFGŠDBBCDBBDDDCDFP
4
=CDF
DŠŠŠCEBEGFDDDDDDGDDCDDC
ŠBCDEFGŠ16151316428B151617121
5327D
5
=C83D345133715E12F456141
116
G10111710416
ŠBCDEFGŠDBBCDBEBDDDCDFEP
5