Luận văn tốt nghiệp Phan Thanh Long
Chơng 4
Đờng đi ngắn nhất trong đồ thị
Giới thiệu:
Trong các ứng dụng thực tế bài toán tìm đờng đi ngắn nhất giữa hai đỉnh của một
đồ thị liên thông có ý nghĩa rất lớn. Bài toán tìm đờng đi ngắn nhất đợc ứng dụng
trong thực tế nh để chọn một hành trình tiết kiệm nhất (về thời gian hoặc chi phí)
trên một mạng giao thông đờng thuỷ, đờng bộ hoặc đờng không. Bài toán lập lịch
thi công các công đoạn trong một công trình thi công lớn. Bài toán lựa chọn đờng
truyền tin với chi phí nhỏ nhất trong mạng thông tin... Dùng thuật giải đờng đi
ngắn nhất trong đồ thị giải quyết bài toán sửa gói tin sai trong việc truyền tin... dới
đây ta xét một số thuật toán để tìm đờng đi ngắn nhất trong đồ thị có trọng số và
đồ thị không có trọng số.
I. Đờng đi ngắn nhất trong đồ thị không có trọng số
1. Định nghĩa: Đồ thị không có trọng số là đồ thị hữu hạn trên các cạnh không
có trọng số. Bài toán tìm đờng đi ngắn nhất giữa hai đỉnh a,b trong đồ thị không
có trọng số G = <X, U> là tìm đờng đi giữa hai đỉnh a, b sao cho có số các cạnh
(cung) là ít nhất.
2. Thuật toán:
Bớc 1: Tại đỉnh a ta ghi số 0
Các đỉnh có cạnh đi từ đỉnh a đến ta ghi số 1.
Giả sử ta đã ghi tới i, tức là ta đã đánh số đợc các tập đỉnh là A(0) = {a}, A(1),
A(2), ... , A(i) trong đó A(i) là tập tất cả các đỉnh đợc ghi bởi số i. Ta xác định tập
đỉnh đợc đánh số bởi số i + 1 là A(i+1) = {x / x X, x A(k) với k = 0, ...,i và
tồn tại y A(i) sao cho từ y có cạnh (cung) tới x}. Do tính hữu hạn của đồ thị, sau
một số hữu hạn các bớc, thuật toán dừng lại và cho kết quả là tập các đỉnh có chứa
b đợc đánh số bởi m là A(m).
Bớc 2: Do bớc 1 thì đỉnh b đợc đánh số bởi m, điều này chứng tỏ đờng đi từ a đến
b có m cạnh (cung) và là đờng ngắn nhất đi từ a đến b. Để tìm tất cả các đờng có
độ dài m ngắn nhất đi từ a đến b, ta xuất phát từ b đi ngợc về a theo đúng nguyên
tắc sau đây:

8
}
A(3) = {x
3
, b, x
9
}
Bớc 2: Từ bớc 1 ta có b A(3) nên từ a đến b là đờng đi ngắn nhất có 3 cung.
Tiếp theo ta xác định tất cả các đờng đi ngắn nhất có độ dài 3:
Đỉnh có cung về b đợc đánh số 2 là x
5
Đỉnh có cung tới x
5
đợc đánh số 1 là x
6
Đỉnh có cung về x
6
đợc đánh số 0 là a
Vậy đờng cần tìm là a - x
6
- x
5
- b.
Ii. Đờng đi ngắn nhất trong đồ thị có trọng số
1. Các khái niệm
Cho đồ thị hữu hạn G = <X, U> với mỗi cạnh u U ta đặt tơng ứng với số dơng
l(u) gọi là trọng số của u.
Đồ thị có cạnh nh trên đợc gọi là đồ thị có trọng số.
Gọi là một đờng đi nào đó trong G = <X, U>
Giả sử = xi

x
1
x
2
x
3
x
4
x
7
x
8
x
9
x
10
x
6
x
5
b
a
0
1
2 3
3
3
2
1
1

n
nh vậy thì ta đi về đỉnh kề với b có trọng số cạnh (cung) từ đỉnh đó về b là
ít nhất.
Từ đỉnh xi
n
ta đi ngợc về đỉnh xi
n-1
có tính chất (xi
n
) = (i
n-1
) + l(xi
n-1
, xi
n
) nếu
không đi về đỉnh kề với xi
n
mà trọng số cạnh (cung) giữa chúng là ít nhất.
Bằng cách đó ta sẽ đi về đỉnh xi
1
mà đỉnh kề là a sao cho (xi
1
) = (a) + l(a, xi
1
) =
l(a, xi
1
) với (a) = 0.
Đờng = axi

n
) - (xi
n-1
)] + [(b) - (xi
n
)] = (b) (1)
Giả sử D(a, b) là 1 đờng bất kỳ từ a đến b và có dạng:
= aj
1
xj
2
... xj
k-1
xj
k
b. Theo bớc 2 ta có bất đẳng thức sau:
44
Luận văn tốt nghiệp Phan Thanh Long
l(a, xj
1
) (xj
1
) - (a) = (xj
1
)
l(xj
1
, xj
2
) (xj

) + l(xj
k
, b) (b) (2)
So sánh (1) và (2) ta có:
l() = min{ l() / D(a, b)}
2.2 Thuật toán Dijkstra
Có thể khái quát thuật toán bằng thủ tục sau:
Procedure Dijikstra(G: đồ thị liên thông có trọng số dơng)}
{G: có các đỉnh a = v
0
, v
1
, ..., v
n
= b và trọng số l(v
i
, v
j
) =

nếu (v
i
, v
j
)

U
của G}
For i:=1 to n (vi) := ;
(a) := 0;


X là đỉnh xuất phát.
t(i, j) với i, j

X là ma trận trọng số
Output: Với x

X tìm các

(x) bé nhất và Truoc(x) để ghi nhận đỉnh đi trớc x
trong các đờng đi ngắn nhất từ a đến x.
}
Begin
{Khởi tạo}
For x X do Begin
(x) := t[a, x];
Truoc[x] := a;
End;
(a) := 0;
For k:=1 to n - 2 do
For x X \ {a} do
For y X do
if (x) > (y) + t[y, x] then begin
(x) := (y) + t[y, x];
Truoc(x) := y;
End;
End;
Độ phức tạp của thuật toán là O(n
3
) chúng ta có thể chấm dứt vòng lặp theo k