Tài liệu chuyên Tin 11 Hà Tây
Phần 3
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 trng : Đặc trng 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 cha tới .
B ớc 2 - Sửa nhãn :
Vòng lặp :
Begin
+ Chọn một đỉnh i trong các đỉnh cha 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 cha tới theo công thức quy hoạch động
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

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 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 ).
Procedure DgdiFB;
Var i,j,k : Integer;
Begin
_______________________
Phần 3 : Đờng đi ngắn nhất TDH 9/2/2013 9/2/2013 D[i,j] = Min { D[i,k] + D[k,j] } k
66
i
k
j
Tài liệu chuyên Tin 11 Hà Tây
For k:=1 to N do
For i:=1 to N do
For j := 1 to N do
if A[i,k]^.dd +A[i,k]^.dd <A[i,j]^.dd then
Begin
A[i,j]^.dd := A[i,k]^.dd +A[i,k]^.dd ;
A[i,j]^.đỉnh := k;
End;
End;

For j:=1 to n do A^[i,j] := MaxInt;
While not Seekeof(F) do
Begin
Read(F,i,j);
If i=0 then
Begin Close(F);Exit;End;
_______________________
Phần 3 : Đờng đi ngắn nhất TDH 9/2/2013 9/2/2013
67
Tµi liÖu chuyªn Tin 11 Hµ T©y
Readln(F,A^[i,j]);
End;
For i:=1 to N do A^[i,i] := 0;
Close(F);
End;
Procedure Lam;
Var NH : Nhan;
dd : Dau;
i,j : Byte;
Procedure Khoitao;
Var i : Byte;
Begin
For i:=1 to N do
Begin
NH[i].h := MaxInt;
DD[i] := False;
End;
NH[xp].h := 0;
NH[xp].t := 0;
End;

68
Tµi liÖu chuyªn Tin 11 Hµ T©y
i := NH[i].t;
End;
For i:=1 to Length(S) do Write(Ord(S[i]),' ');
End;
Begin
Clrscr;
Khoitao;
While Not DD[d] do
Begin
i := Min;
If i=0 then
Begin
Writeln('vo nghiem ');
Exit;
End;
Sua(i);
End;
Lannguoc;
End;
BEGIN
Clrscr;
DocF;
Lam;
Dispose(A);
Writeln('Da xong ');
Readln;
END.
Input

NÕu xp=1,d=8 th× cã ®êng ®i 1 4 6 5 8
NÕu xp=8,d=1 th× cã ®êng ®i 8 6 3 2 1
Bµi 2 : B»ng thuËt to¸n For-Bellman t×m ®êng ®i ng¾n nhÊt tõ xp tíi ®
Uses Crt;
Const Max = 100;
Fi = 'Duongdi.inp';
Type Ta = Array[1..Max,1..Max] of Record h : Word;tg : Byte; End;
Dau = Array[1..Max] of Boolean;
Var N,xp,t : Integer;
A : ^Ta;
_______________________
PhÇn 3 : §êng ®i ng¾n nhÊt TDH 9/2/2013 9/2/2013
69