Luận văn tốt nghiệp
42
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.

ik
tìm tất cả các đỉnh có cạnh (cung) với x
ik
(k = 1, 2, ...) được
ghi số m -2.
Bằng cách lùi dần trở lại, đến một lúc nào đó gặp đỉnh ghi số 0, đó chính là đỉnh
a. Tất cả các đường xác định theo các bước trên là đường đi từ a đến b có độ dài
ngắn nhất là m cần tìm.

Hình 1.1

Ví dụ đồ thị như hình 1.1 xây dựng đường đi ngắn nhất theo thuật toán trên:
Bước 1: Đỉnh a được đánh số 0 và có A(0) = {a}
A(1) = {x
1
, x
6
, x
7
}
A(2) = {x
2
, x
5

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ử

= x
i
1
u
i
1
x
i
2
u
i
2
... x
i
n - 1
u

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


X nếu độ dài đường đi từ đỉnh xuất phát tới đỉnh x có trọng số là l(

)
thì

(x) = l(

) gọi là trọng số của đỉnh x. Cơ sở của tất cả các thuật toán tìm
đường đi ngắn nhất là xác định được các trọng số nhỏ nhất cho tất cả các đỉnh từ
đó tìm đường đi ngắn nhất.
Bước 1: Đánh trọng số các đỉnh, trọng số của đỉnh xuất phát là

(a) = 0.
Tại các đỉnh còn lại ta ghi một số dương nào đó sao cho nó đủ lớn hơn trọng số
của các đỉnh từ a tới.
Bước 2: Thực hiện việc giảm trọng số các đỉnh. Giả sử tại đỉnh x được ghi trọng
số

(x). Nếu tồn tại đỉnh y có trọng số

(y) từ y sang x mà

(x) >

(y) + l(y, x)
thì ta thay trọng số của

(x) bởi trọng số


n
, b). Nếu không có
đỉnh kề với x
i
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 x
i
n
ta đi ngược về đỉnh x
i
n-1
có tính chất

(x
i
n
) =

(
i
n-1
) + l(x
i
n-1
, x
i
n
)

i
2
... x
i
n - 1
x
i
n
b là đường đi từ a đến b có trọng số ít nhất trong
số tất cả các đường từ a đến b.
Thật vậy l(

) = l(a,x
i
1
) + l(x
i
1
,x
i
2
) + ... + l(x
i
n-1
,x
i
n
) + l(x
i
n


(b) -

(x
i
n
)] =

(b) (1)

Giả sử



D(a, b) là 1 đường bất kỳ từ a đến b và có dạng:
Luận văn tốt nghiệp
45

= a
j
1
x
j
2
... x
j
k-1




(x
j
2
) -

(x
j
1
)
.....................................
l(x
j
k-1
,x
j
k
)



(x
j
k
) -

(x
j

, x
j
k
) + l(x
j
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


While b



S Begin
u:= đỉnh không thuộc S có

(u)
nhỏ nhất;
S := S

{u};
For tất cả các đỉnh v không thuộc S
if (u) + l(u,v) < (v) then (v) := (u) + l(u,v)
{thêm vào S đỉnh có trọng số nhỏ nhất và sửa đổi trọng số của các đỉnh
không thuộc S}
End;
{l(

) = l(a, b) = độ dài đường đi ngắn nhất từ a đến b}

Độ phức tạp của thuật toán là O(n
2
), tức là phải dùng O(n
2
) phép cộng và so
sánh đường đi ngắn nhất giữa 2 đỉnh trong đồ thị đơn vô hướng liên thông có
trọng số.
2.3 Thuật toán Ford - Bellman

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
khi phát hiện trong quá trình thực hiện 2 vòng lặp trong không có biến d[u] nào
bị thay đổi giá trị. Đối với những đồ thị có số cạnh m thoả mãn m < 6.n thì tốt
hơn là sử dụng danh sách kề để biểu diễn đồ thị, khi đó vòng lặp theo y cần viết
dưới dạng
For tất cả các đỉnh y kề với x do