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

Phần 4 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 .

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 một cách
“ đẹp đẽ bất ngờ “ :
Với 2 đỉnh i và j ( 1 ( i, j ( N ) , đường đi ngắn nhất từ i tới j là D[i,j] rõ ràng là đại lượng nhỏ nhất trong các tổng : D[i,k] + D[k,j] trong đó k là mọi đỉnh trung gian ( con đường đi từ i tới j sẽ đi qua k ).










D[i,j] = Min { D[i,k] + D[k,j] } ( k













Procedure DgdiFB;
Var i,j,k : Integer