Giáo án môn: Lý Thuyết Đồ Thị

Nguyễn Minh Đức - ĐHQG Hà Nội
60
v1
v2
v10
v5
v8
v9
v6
v7
v3 v4
Chng 6
MT S BI TON NG DNG
(Bi toỏn tỡm ng i ngn nht v bi toỏn lung cc i)
6.1 Bi toỏn tỡm ng i ngn nht
6.1.1 Tỡm ng i ngn nht trong th khụng cú trng s
Bi toỏn:

Cho th khụng cú trng s G = (V,E) v hai nh u, v V. Tỡm ng i ngn nht t nh u
n nh v, tc l ng i t u n v cú s cnh (cung) l ớt nht
gii quyt bi toỏn ny ta cú th thc hin theo thut toỏn sau õy:
Thut toỏn:
Bc 1:

Ti nh u ta ghi s 0
Cỏc nh k vi u (cú cnh i t u n) ta ghi s 1
Cỏc nh k vi cỏc nh ó c ghi s 1 ta ghi s 2
Gi s ta ó ghi ti i, tc l ta ó ỏnh s c cỏc tp nh l V(0) = {u}, V(1), V(2), ,V(i). Trong
ú V(i) l tp tt c cỏc nh c ghi bi s i. Ta xỏc nh tp cỏc nh c ỏnh s bi s i+1 nh


Tỡm ng i ngn nht t nh v1

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
61Chu ý:
Thuật toán tìm đường đi giữa hai đỉnh u và v trong đồ thị bằng cách áp dụng thuật toán tìm kiếm
theo chiều rộng chính là đường đi ngắn nhất từ u tới v (theo số cạnh).
6.1.2 Tìm đường đi ngắn nhất trong đồ thị có trọng số
Bài toán:

Cho đồ thị có trọng số G = (V,E) và hai đỉnh s, t ∈V. Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh
t, tức là đường đi từ s đến t có tổng trọng số của các cạnh (cung) là nhỏ nhất.


Ví dụ

Tuy nhiên, trên thực tế việc tìm đường đi ngắn nhất giữa hai đỉnh lại có rất nhiều trường hợp riêng
biệt mà chưa có một thuật toán nào thực sự tối ưu được tất cả, chẳng hạn đồ thị có trọng số của cạnh
là một số âm, hay đồ thị có chứa chu trình có trọng số âm Sau đây ta sẽ xét qua môt số trường hợp
riêng.

6.1.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Ford – Bellman)
Thuật toán tìm đường đi ngắn nhất từ một đỉnh s đến tất cả các đỉnh còn lại của đồ thị được đưa ra
bởi hai nhà bác học Ford và Bellman, thuật toán này làm việc trong trường hợp trọng số của các
cạnh (cung) là tuỳ ý, nhưng giả thiết rằng trong đồ thị không có chu trình âm. Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
62
Procedure Ford_Bellman;
(*
Đầu vào: Đồ thị G = (V,E) với n đỉnh,
s
∈V là đỉnh xuất phát, c[u,v] là ma trận trọng số;
Đầu ra: Khoảng cách ngắn nhất từ s đến tất cả các đỉnh còn lại d[v],
Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v;
Giả thiết: Đồ thị không có chu trình âm;
*)
Begin

(*
Đầu vào: Đồ thị G=(V,E) với n đỉnh cho bởi ma trận trọng số c[i,j]
s
∈V là đỉnh xuất phát
Đầu ra: Khoảng cách từ đỉnh s đến tất cả các đỉnh v còn lại là d[v]
Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v
Giả thiết: Trọng số các cạnh (cung) của đồ thị là không âm
*)
Begin
(* Khởi tao *)
For v
∈V do
Begin
d[v]:=c[s,v];
Truoc[v]:=s;
End;
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
63
d[s]:=0; T:=V\{s}; (* T là tập các đỉnh có nhãn tạm thời *)
(* Bước lặp *)
While T
φ
≠ do
Begin
Tìm đỉnh u thuộc T thoả mãn: d[u] = min{d[z]; z thuộc T};
T:=T\{u}; (* Cố định nhãn của đỉnh u *)
for v thuộc T do (*Gán lại nhãn cho các đỉnh *)
if d[v]>d[u] + c[u,v] then