CÁC BÀI TOÁN ĐƯỜNG ĐI
1
NỘI DUNG

Đường đi ngắn nhất
Bài toán
Nguyên lý Bellman
Thuật toán Dijkstra
Thuật toán Floyd
Thuật toán Ford-Bellman
2
ĐƯỜNG ĐI NGẮN NHẤT
3
CB
A
E
D
F
0
328
5 8
4
8
7 1
2 5
2
3 9
Cho đồ thị có hướng có trọng G=(X, E) và hai đỉnh s, t ∈X,
gọi P là một đường đi từ đỉnh s đến đỉnh t, trọng lượng
(hay giá) của đường đi P được định nghĩa là:
L(P) = ∑

L(P)→ -∞.
ĐIỀU KIỆN TỒN TẠI LỜI GiẢI
6
s
t
k
µ

Ma trận trọng lượng L
NxN
được định nghĩa:
L
ij
= trọng lượng cạnh nhỏ nhất nối i đến j nếu có,
L
ij
= ∞ nếu không có cạnh nối i đến j.

Khi cài đặt thuật toán có thể dùng 0 thay cho ∞ bằng
cách đưa thêm một số kiểm tra thích hợp.
DỮ LIỆU NHẬP
7
C
A
B
D
12
7
15
5

= trọng lượng cạnh nhỏ nhất nối i đến j nếu có,
L
ij
= ∞ nếu không có cạnh nối i đến j.

Khi cài đặt thuật toán có thể dùng 0 thay cho ∞ bằng
cách đưa thêm một số kiểm tra thích hợp.
DỮ LIỆU NHẬP
8
C
A
B
D
12
7
15
5
16













1
là đường đi con của P từ s đến k
và P
2
là đường đi con của P từ k đến t. Khi đó P
1
cũng là
đường đi ngắn nhất từ s đến k.
NGUYÊN LÝ BELLMAN
10
L(P
1
’) < L(P
1
) ⇒ L(P
1
’⊕P
2
) < L(P
1
⊕P
2
)=L(P)
s
t
k
P
1
P
1

vk
thì
D[k] = D[v]+L
vk
và Labels[k]=v
THUẬT TOÁN DIJKSTRA
12
VÍ DỤ
13
d(z) = 75

d(u) = 50
1
0
z
s
u
d(z) = 60

d(u) = 50
1
0
z
s
u
Cập nhật độ dài ĐĐ từ s đến đỉnh z: 75  60
VÍ DỤ
Đồ thị G gồm 7 đỉnh, 12
cạnh như hình bên. Tìm
đường đi ngắn nhất từ đỉnh














∞∞∞∞
∞∞∞∞∞
∞∞∞∞∞
∞∞∞
∞∞∞∞∞
∞∞∞∞∞
∞∞∞
042
120
170
8014
50
80
6390
VÍ DỤ
V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có
màu xanh lá

∞ -1
∞ -1
VÍ DỤ
16
9
1
2
3
4
5
6
7
3
4
8
1
5
6
2
4
17
12
8
0
-1
9
1
∞
-1
∞

7
4
4
4
11
4
6
1
∞ -1
3 1
V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có
màu xanh lá
VÍ DỤ
18
9
1
2
3
4
5
6
7
3
4
8
1
5
6
2
4

1
5
6
2
4
17
12
8
0
-1
7
4
4
4
9
3
6
1
∞ -1
3 1
V: đỉnh chưa bị tô màu; D[k]: số có màu đỏ; Labels[k]: số có
màu xanh lá
VÍ DỤ
ĐĐNN từ 1 đến 5 có trọng lượng D[5]=9: 5  3  4  1
20
9
1
2
3
4

∞ ∞ ∞ ∞ ∞ ∞
1 9
∞
3
∞ ∞
6
2 7 4 11
∞
6
3 7 9
∞
6
4 7 9
∞
5 9
∞
1 2 3 4 5 6 7
0 -1 -1 -1 -1 -1 -1 -1
1 1 -1 1 -1 -1 1
2 4 4 4 -1 1
3 4 3 -1 1
4 4 3 -1
5 3 -1
D
Labels
VÍ DỤ
22
CB
A
E

0
328
5 8
4
8
7 1
2 5
2
3 9
CB
A
E
D
F
0
327
5 8
4
8
7 1
2 5
2
3 9
VÍ DỤ
23
CB
A
E
D
F

THUẬT TOÁN DIJKSTRA – CÀI ĐẶT
Graph Graph::PrintPath(int s, int t)
{
int temp[MAX];
int dem = 0;
//In đường đi ngắn nhất từ s đến t dựa vào Labels
while(Labels[t] != -1)
{
temp[dem++]=t;
t=Labels[t];
}
temp[dem++]=s;
while (dem > 0)
printf(“%d “, temp[ dem]);
}