Tài liệu chuyên Tin 11 Hà Tây
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 trng : Đặc trng 1 ghi nhận đỉnh kề đi tới i , đặc
trng 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;
III / Bài tập mẫu :
Bài 1 : Cho đồ thị vô hớng liên thông từ File DGDI.INP tổ chức nh sau :
+ Dòng thứ nhất ghi 3 số : N,xp,đ ( số đỉnh , tên đỉnh xuất phát , đỉnh đích )
+ Các dòng tiếp theo : mỗi dòng 3 số : i,j , A[i,j] ( A[i,j] là khoảng cách i tới j )
Nếu i=0 thì kết thúc dữ liệu về đồ thị này
Bằng thuật toán Di jsktra tìm đờng đi ngắn nhất từ xp tới đ D[i,j] = Min { D[i,k] + D[k,j] } k
54
i
k
j
Tài liệu chuyên Tin 11 Hà Tây
Bài 2 : Nội dung nh trên nhng tìm đờng đi ngắn nhất bằng thuật toán For-Bellman
Lời giải :
Bài 1 : Bằng thuật toán Di jsktra tìm đờng đi ngắn nhất
Uses Crt;
Const Max = 100;
Fi = 'duongdi.inp';
Type Ta = Array[1 Max,1 Max] of Integer;
Re = Record
t : Byte;
h : Word;
End;
Nhan = Array[0 Max] of Re;
Dau = Array[1 Max] of Boolean;
Var N,xp,d : Byte;
A : ^Ta;

DD[i] := False;
End;
_______________________
Phần 4 : Đờng đi ngắn nhất TDH 9/7/2014 9/7/2014
55
NH[xp].h := 0;
NH[xp].t := 0;
End;
Function Min : Byte;
Var i,k : Byte;
Begin
i := 0;
For k:=1 to N do
If (Not DD[k]) and (NH[k].h<NH[i].h) then i := k;
Min := i;
End;
Procedure Sua(i : Byte); {i : dinh cuoi cua hanh trinh hien tai }
Var j : Byte;
Begin
DD[i] := True;
For j:=1 to N do
If (Not DD[j]) and (NH[j].h>NH[i].h+A^[i,j]) then
Begin
NH[j].h := NH[i].h+A^[i,j];
NH[j].t := i;
End;
End;
Procedure Lannguoc;
Var S : String;
i,j : Byte;

Lam;
Dispose(A);
Writeln('Da xong ');
Readln;
END.
Input
8 1 8
1 2 3
2 1 3
1 3 5
3 1 5
1 4 2
4 1 2
2 3 1
3 2 1
2 5 7
5 2 7
3 4 4
4 3 4
3 5 5
5 3 5
4 6 3
6 4 3
5 8 3
8 5 3
6 7 4
7 6 4
6 8 6
8 6 6
7 8 5

For i:=1 to N do A^[i,i].h := 0;
While Not SeekEof(F) do
Begin
_______________________
PhÇn 4 : §êng ®i ng¾n nhÊt TDH 9/7/2014 9/7/2014
57
Read(F,i,j);
If i=0 then
Begin
Close(F);
Exit;
End;
Readln(F,A^[i,j].h);
End;
Close(F);
End;
Procedure FB;
Var i,j,k : Integer;
Begin
For k:=1 to N do
For i:=1 to N do
For j:=1 to N do
If (A^[i,k].h+A^[k,j].h<A^[i,j].h) then
Begin
A^[i,j].h := A^[i,k].h+A^[k,j].h;
A^[i,j].tg := k;
End;
End;
Procedure Lannguoc;
Var S : String;

1 )
_______________________
PhÇn 4 : §êng ®i ng¾n nhÊt TDH 9/7/2014 9/7/2014
59