Đường đi ngắn nhất giữa các cặp đỉnh
Rõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ chọn s lần lượt là các đỉnh của đồ thị. Rõ ràng, khi đó ta thu được thuật toán với ...
Rõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ chọn s lần lượt là các đỉnh của đồ thị. Rõ ràng, khi đó ta thu được thuật toán với độ phức tạp O(n4) (nếu sử dụng thuật toán Ford_Bellman) hoặc O(n3) đối với trường hợp trọng số không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát, sử dụng thuật toán Ford_Bellman n lần không phải là cách làm tốt nhất. Ở đây ta sẽ mô tả một thuật toán giải bài toán trên với độ phức tạp tính toán O(n3): thuật toán Floyd. Thuật toán được mô tả trong thủ tục sau đây.
Procedure Floyd
Procedure Floyd;
(* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
Đầu vào: Đồ thị cho bởi ma trận trọng số a[i,j], i, j =1, 2,. . ,n.
Đầu ra:
Ma trận đường đi ngắn nhất giữa các cặp đỉnh
d[i,j]=, i,j = 1, 2. . .,n,
trong đó d[i,j] cho độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j.
Ma trận ghi nhận đường đi
p[i,j], i, j = 1, 2.. . , n,
trong đó p[i,j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất từ i đến j. *)
begin
(* Khởi tạo *)
for i:=1 to n do
for j:=1 to n do
begin
d[i,j]:=a[i.j];
p[i.j]:=i;
end;
(* Bước lặp *)
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if d[i,j]>d[i,k]+d[k,j] then
begin
d[i,j]+d[i,k]+d[k,j];
p[i,j]>p[k,j];
end;
end;
Rõ ràng độ phức tạp tính toán của thuật toán là O(n3).
Kết thúc phần này chúng ra trình bày một cách thể hiện thuật toán Dijkstra trên ngôn ngữ Pascal:
(* CHƯƠNG TRÌNH TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ ĐỈNH S ĐẾN ĐỈNH T THEO THUẬT TOÁN DIJKSTRA *)
uses crt;
const max=50;
var
n, s, t:integer;
chon:char;
Truoc:array[1..max] of byte;
d: array[1..max] of integer;
a: array[1..max,1..max] of integer;
final: array[1..max] of boolean;
procedure Nhapsolieu;
var
f:text;
fname:string;
i,j:integer;
begin
write(‘Vao ten file du lieu can doc:’);
readln(fname);
assign(f,fname);
reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do read(f, a[i,j];
close(f);
end;
procedure Insolieu;
var
i,j:integer;
begin
writeln(‘So dinh cua do thi:’,n);
writeln(‘Ma tran khoang cach:’);
for i:=1 to n do
begin
for j:=1 to n do write(a[i,j]:3,’ ‘);
writeln;
end;
end;
Procedure Inketqua;
Var
i,j:integer;
begin
writeln(‘Duong di ngan nhat tu ‘,s,’ den ‘,t);
write(t,’ → ’);
while i<> s do
begin
i:=Truoc[i];
write(i,’ → ’);
end;
end;
Procedure Dijkstra;
Var
U,v,minp:integer;
Begin
Write(‘Tim duon di tu s=’);Readln(s);Write(‘ den t=’);Readln(t);
For v:=1 to n doBegin
d[v]:=a[s,v];
Truoc[v]:=s;
Filal[v]:=false;
End;
Truoc[s]:=0;D[s]:=0;Final[s]:=true;
While not final[t] do (* Buoc lap *)Begin
{ Tim u la dinh co nhan tam thoi nho nhat }
minp:=maxint;
for v:=1 to n do
if (not final[v]) ans minp>d[v]) then
begin
u:=v; minp:=d[v];
end;
final[u]:=true;
if not final[t] then
for v:=1 to n do
if (not final[v]) and (d[u]+a[u,v]<d[v]) then
begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
end;
End;
end;
Procedure Menu;
Begin
Clrscr;
Writeln(‘1. Nhap du lieu tu file’);
Writeln(‘2. Giai bai toan’);
Writeln(‘3. Ket thuc’);
Writeln(‘---------------------‘);
Write(‘Hay chon chuc nang:’):
End;
(* Chuong trinh chinhs *)
Begin
Repeat
Menu;
Chon:=readkey;
Writeln(chon);
Case chon of
‘1’:Nhapsolieu;
‘2’: begin
Insolieu;
Dijkstra;
Inketqua;
‘3’:exit;
end;
Until false;
End.
