Tài liệu HSG Pascal Phần 5

Phần 5
Tìm đường đi ngắn nhất
Thuật toán di jsktra và ford-bellman

Một bài toán thường gặp trên đồ thị là tìm đường đi ngắn nhất từ đỉnh thứ nhất (ký hiệu là xp ) tới đỉnh thứ hai ( ký hiệu là đ ). Khi vét cạn duyệt mọi đường đi từ xp tới đ , nếu không chú ý các cận ( trên hoặc dưới ) thích hợp để tránh các đường đi không tới đích , có thể duyệt không hết được khi đồ thị nhiều cung . Sau đây là 2 thuật toán giúp tránh tình trạng đó trong nhiều đồ thị.

I / Thuật toán Di jsktra ( gán nhãn ) :

Tư tưởng của thuật toán là trong quá trình xây dựng đường đi từ xp tới đ ,luôn kết hợp với việc chọn lựa đường đi để nó tốt dần lên bằng cách thay đổi liên tục nhãn tại các đỉnh .Mỗi đỉnh i sẽ có nhãn gồm 2 đặc trưng : Đặc trưng 1 ghi nhận đỉnh kề đi tới i , đặc trưng 2 ghi nhận độ dài đường đi ngắn nhất từ đỉnh xp tới đỉnh i này . Do đó khi tới đỉnh cuối cùng ta có ngay đường đi ngắn nhất . Các bước của thuật toán như sau :

Bước 1 - Khởi trị :
+ Nhãn đỉnh xuất phát là xp(0,0) : đỉnh đi tới đỉnh xp là đỉnh 0 ,đường đi đã qua là 0 .Các đỉnh i còn lại có nhãn là i (0, ( ) : có nghĩa đỉnh tới i là đỉnh 0 , đường đã qua tới i là vô cùng lớn .
+ Khởi trị mảng đánh dấu : Các đỉnh đều chưa tới .

Bước 2 - Sửa nhãn :
Vòng lặp :
Begin
+ Chọn một đỉnh i trong các đỉnh chưa tới và có nhãn độ dài nhỏ nhất . Đánh dấu đã tới đỉnh i.
+ Sửa lại nhãn các đỉnh k chưa tới theo công thức quy hoạch động

Nhãn[ k] = Min { Nhãn[k] , Nhãn[i] + A[i,k] }





End;
Cho đến khi tới đỉnh đích .


Bước 3 - Lần ngược ,hiện đường đi ngắn nhất :
+ Bắt đầu : đỉnh := đ ; cs := 1 ; KQ[cs] := đỉnh ;
+ Vòng lặp
Begin
đỉnh := Nhãn thứ nhất của đỉnh ;
Inc(cs);
KQ[cs] := đỉnh;
End;
Cho đến khi đỉnh = xp;
+ Duyệt ngược mảng KQ để hiện hành trình
+ Hiện độ dài đường đi .

Tìm đường đi ngắn nhất giữa 2 đỉnh a và z : ( Mảng nhãn là mảng L )

procedure dijkstra(w,a,z,L)
begin L(a) := 0;
for tất cả các đỉnh x khác a do L(x) := (
T := tập tất cả các đỉnh
while z ( T do
begin
chọn v ( T với L(v) nhỏ nhất
T := T-{v}
For với mỗi x( T và có cạnh nối tới v do
L(x) := min {L(x) ,L(v)+w(v,x)}
end
end

II / Thuật toán Ford - BellMan :

Bằng 3 vòng For đơn giản , thuật toán đã thể hiện tinh thần quy hoạch động