Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất - Nguyễn Trần Phi Phượng

Chương 5
BÀI TOÁN ĐƯỜNG ĐI 
NGẮN NHẤT
209/04/2011
ƒBài toán: Cho G = là đồ thị có trọng số. s và t là
2 đỉnh của đồ thị. Hãy tìm đường đi có tổng trọng số nhỏ
nhất từ s đến t.
VD:
ƒ Đường đi ngắn nhất từ Etna đến Oldtown là: Etna – Bangor – Orono –
OldTown
ƒ Đường đi ngắn nhất từ Hermae đến Etna là: Hermae – Hampdea – Bangor -
Etna
15
5
9
3
5
20
15
5
9
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
Lý thuyết đồ thị
309/04/2011
Tìm đường đi ngắn nhất từ đỉnh 3 đến đỉnh 5
– Trả lời: 3 – 1 – 2 – 5 ??? Độ dài 11 là ngắn nhất ???
– Đường đi này thì sao? Độ dài là bao nhiêu?
3 – 1 – 2 – 5 – 2 – 5 
– Đường đi trên đã ngắn nhất chưa???
1 2
3 4 5
20
10
7
9
9
- 6 
4 
5 
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
Lý thuyết đồ thị
409/04/2011
Điều kiện để bài toán có lời giải:
– Phải tồn tại đường đi từ s đến t:
• Đồ thị vô hướng liên thông
• Đồ thị có hướng liên thông mạnh
• Đồ thị vô hướng, s và t nằm trong cùng một thành phần
liên thông
• Đồ thị có hướng, có tồn tại đường đi từ s đến t
– Trong đồ thị không tồn tại chu trình âm
• Đồ thị có hướng: không tồn tại chu trình âm.
• Đồ thị vô hướng: không tồn tại cạnh âm.
1 2 3
4 5 6
5 7
2
‐ 3 
8
1
6
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
Lý thuyết đồ thị
509/04/2011
Nhận xét:
– Nếu v là đỉnh trung gian trên đường đi ngắn nhất từ s
đến t thì đường đi từ s đến v phải là ngắn nhất và
đường đi từ v đến t cũng phải là ngắn nhất.
– Do đó, để tối ưu, người ta mở rộng bài toán tìm
đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh
còn lại của đồ thị.
 s v t
X
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
Lý thuyết đồ thị
609/04/2011
Ý tưởng chung của các thuật toán tìm đường đi ngắn nhất
– Dò tìm bằng cách thử đi qua các đỉnh trung gian
– Nếu phát hiện đường đi qua đỉnh trung gian ngắn hơn
đường đi hiện tại thì sẽ cập nhật đường đi mới, đồng thời
chỉnh sửa các thông tin liên quan.
– Sử dụng hai mảng để lưu trữ tạm thời:
• Mảng d[v]: Lưu trữ độ dài đường đi ngắn nhất hiện tại
từ s đến v.
• Mảng T[v]: Lưu trữ đỉnh nằm trước v trên đường đi
ngắn nhất hiện tại.
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
Lý thuyết đồ thị
709/04/2011
s v
u
Truoc[v]
d[v]
d[u]
c[u,v]
X
if (d[v] > d[u] + c[u,v])
{ d[v] = d[u] + c[u,v];
Truoc[v] = u;
}
Lý thuyết đồ thị
5.1 Đồ thị có trọng số - Bài toán đường đi ngắn nhất
809/04/2011
//Khởi tạo
for v ∈ V
{
d[v]=c[s,v];
Truoc[v]=s;
}
//Bắt đầu
d[s]=0;
for (k=1; k<=n-2; k++)
for v ∈ V\{ s}
for u ∈ V
if (d[v] > d[u] +c[u,v])
{
d[v]=d[u]+c[u,v];
Truoc[v]=u;
}
k 1 2 3 4 5
0,1 1,1 ∞ ,1 ∞ ,1 3,1
1 0,1 1,1 4,2 4,2 -1,3
2 0,1 1,1 4,2 3,5 -1,3
3 0,1 1,1 4,2 3,5 -1,3
5.2 Thuật toán Ford-Bellman
Lý thuyết đồ thị
909/04/2011
Cây kết quả:
k 1 2 3 4 5
0,1 1,1 ∞ ,1 ∞ ,1 3,1
1 0,1 1,1 4,2 4,2 -1,3
2 0,1 1,1 4,2 3,5 -1,3
3 0,1 1,1 4,2 3,5 -1,3
1
2
3
5
4
5.2 Thuật toán Ford-Bellman
Lý thuyết đồ thị
1009/04/2011
k 1 2 3 4 5 6
0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1
1 0,1 1,1 6 ,2 3 ,2 7,4 7,3
2 0,1 1,1 4 ,4 3 ,2 7,4 5,3
3 0,1 1,1 4 ,4 3 ,2 6,6 5,3
4 0,1 1,1 4 ,4 3 ,2 6,6 5,3S = 1
5.2 Thuật toán Ford-Bellman
Lý thuyết đồ thị
1109/04/2011
k 1 2 3 4 5 6
0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1
1 0,1 1,1 6 ,2 3 ,2 7,4 7,3
2 0,1 1,1 4 ,4 3 ,2 7,4 5,3
3 0,1 1,1 4 ,4 3 ,2 6,6 5,3
4 0,1 1,1 4 ,4 3 ,2 6,6 5,3
Cây kết quả
1
2
4
3
6
5
5.2 Thuật toán Ford-Bellman
Lý thuyết đồ thị
1209/04/2011
ƒNhận xét:
– Áp dụng được cho mọi trường hợp
– Chi phí tính toán lớn do dùng 3 vòng lặp lồng nhau
– Thường lãng phí một số bước sau cùng
ƒCải tiến:
– Không thể cải tiến tốt hơn cho trường hợp tổng quát
– Chỉ có thể làm tốt hơn cho một số trường hợp riêng
5.2 Thuật toán Ford-Bellman
Lý thuyết đồ thị
1309/04/2011
k 1 2 3 4 5 6
0,1 1,1 ∞ ,1 ∞ ,1 ∞,1 ∞,1
1 0,1 1,1 6 ,2 3 ,2 7,4 7,3
2 0,1 1,1 4 ,4 3 ,2 7,4 5,3
3 0,1 1,1 4 ,4 3 ,2 6,6 5,3
4 0,1 1,1 4 ,4 3 ,2 6,6 5,3
ƒNhận xét về Ford-Bellman:
– Kết quả của bảng đã ổn định từ sớm
– Trên một dòng, giá trị d nhỏ nhất không thay đổi về sau nếu
trọng số các cạnh là không âm
5.3 Thuật toán Dijkstra
Lý thuyết đồ thị
1409/04/2011
Chú ý: thuật toán này chỉ dùng cho đồ thị không có cạnh
âm.
Ý tưởng:
– Do không có cạnh âm nên tại mỗi bước, sẽ có một đỉnh
mà thông tin về nó sẽ không thay đổi về sau
– Tại mỗi bước, ta không cần phải kiểm tra qua tất cả các
đỉnh trung gian, mà chỉ thực hiện như sau:
• Chọn một đỉnh u có giá trị d[u] nhỏ nhất
• Chọn u làm đỉnh trung gian để xác định các bước kế
tiếp
5.3 Thuật toán Dijkstra
Lý thuyết đồ thị
1509/04/2011
//Khởi tạo
for v ∈ V
{
d[v]=c[s,v];
Truoc[v]=s;
}
d[s]=0; T=V\{s} ; //T là tập các đỉnh chưa cố định
//Bước lặp
while T != ∅
{
Tìm đỉnh u ∈ T thoả mãn d[u]=min{d[z]:z∈T};
T=T\{u} ; //Cố định nhãn của đỉnh u
For v∈ T
If d[v]>d[u]+c[u,v] then
{
d[v]=d[u]+c[u,v];
Truoc[v]=u;
}
}
k 1 2 3 4 5 6
0,1 1,1* ∞,1 ∞,1 ∞,1 ∞,1
1 6,2 3,2* ∞,1 8,2
2 4,4* 7,4 8,2
3 7,4 5,3*
4 6,6*
5.3 Thuật toán Dijkstra
Lý thuyết đồ thị
1609/04/2011
k 1 2 3 4 5 6
0,1 1,1* ∞,1 ∞,1 ∞,1 ∞,1
1 6,2 3,2* ∞,1 8,2
2 4,4* 7,4 8,2
3 7,4 5,3*
4 6,6*
Cây kết quả
1
2
4
3
6
5
5.3 Thuật toán Dijkstra
Lý thuyết đồ thị
1709/04/2011
Thuật toán Floyd
– Đầu vào: Ma trận kề trọng số A
– Đầu ra:
• Ma trận đường đi ngắn nhất: d
• Ma trận lưu đỉnh trước đó trên đường đi: p
5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa
tất cả các cặp đỉnh
Lý thuyết đồ thị
1809/04/2011
// Khởi tạo
For (i=1; i<= n; i++)
For (j=1; j<=n; j++)
{
d[i,j] = a[i,j];
p[i,j] = i;
}
// Bước lặp
For (k=1; k<=n; k++)
For (i=1; i<= n; i++)
For (j=1; j<=n; j++)
If (d[i,j] > d[i,k] + d[k,j])
{
d[i,j] = d[i,k] + d[k,j];
p[i,j] = p[k,j];
}
1 2
34
10
2
1
56
3
10 6 2
10 5 3
6 5 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Ma trận d Ma trận p
5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa
tất cả các cặp đỉnh
Lý thuyết đồ thị
1909/04/2011
1 2
34
10
2
1
56
3
10 6 2
10 5 3
6 5 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Ma trận d Ma trận p
10 6 2
10 5 3
6 5 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
10 6 2
10 5 3
6 5 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
5 3 2
5 4 3
3 4 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 4 4 1
4 2 4 2
4 4 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
10 6 2
10 5 3
6 5 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
Khởi 
tạo
k=1
k=2
k=3
k=4
5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa
tất cả các cặp đỉnh
Lý thuyết đồ thị
2009/04/2011
– Từ 1 đến 3: 
• Trước 3 là p[1,3] = 4. Vậy 4 là đỉnh nằm trước 3 trên đường đi 
này.
• Trước 4 là p[1,4] = 1. Vậy 1 là đỉnh nằm trước 4 trên đường đi 
này.
• Dừng. Đường đi là: 1 – 4 – 3 với độ dài là d[1,3] = 3
– Tương tự, đường đi ngắn nhất từ 3 đến 2 là: 3 – 4 – 2 với độ dài là 
p[3,2] = 4
1 2
34
10
2
1
56
3
5 3 2
5 4 3
3 4 1
2 3 1
∞⎡ ⎤⎢ ⎥∞⎢ ⎥⎢ ⎥∞⎢ ⎥∞⎣ ⎦
1 4 4 1
4 2 4 2
4 4 3 3
4 4 4 4
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
5.4 Thuật toán Floyd – Đường đi ngắn nhất giữa
tất cả các cặp đỉnh
Lý thuyết đồ thị