CÀI ĐẶT THUẬT TOÁN FLOYD-WARSHALL TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH TRONG ĐỒ THỊ CÓ HƯỚNG CÓ TRỌNG SỐ BẰNG CHƯƠNG TRÌNH PASCAL.. Thuật toán Floyd-warshall.. Chương trình dùng thuậ
Trang 1CÀI ĐẶT THUẬT TOÁN FLOYD-WARSHALL TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH TRONG ĐỒ THỊ CÓ HƯỚNG CÓ TRỌNG SỐ BẰNG
CHƯƠNG TRÌNH PASCAL.
Thuật toán Floyd-warshall.
Chương trình dùng thuật toán Floyd-warshall tìm đường
đi ngắn nhất giữa mọi cạp đỉnh trong đồ thị có hướng có trọng số
Dữ liệu được lấy từ tệp FLOYD-WARSHALL.INP có cấu trúc :
n (số đỉnh)
m (số cạnh)
Sau khi lấy dữ liệu, chương trình sẽ xác định có tồn tại đường
đi ngắn nhất, tìm đường đi ngắn nhất đó và lưu vào tệp FLOYD-WARSHALL.OUT có cấu trúc:
D ma trận độ dài đường đi ngắn nhất giữa
mọi cặp đỉnh
…
P ma trận định đường đi ngắn nhất giữa
mọi cặp
Trang 2Chương trình: (FLOYDWAR.PAS)
program floyd_war;
uses crt;
var p,d:array[1 100,1 100] of integer; f:text;
n,m,w:integer;
procedure input;
var i,k,x,trongso:integer;
begin
assign(f,'floydwar.inp');reset(f); readln(f,n,m);
for i:=1 to m do
begin
readln(f,k,x,trongso);
d[k,x]:=trongso;
end;
close(f);
end;
procedure init;
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
if(d[i,j]=0)then
d[i,j]:=300
else p[i,j]:=j;
end;
procedure floydwar;
var k,i,j:integer;
begin
k:=1;
while(k<=n) do
begin
for i:=1 to n do
Trang 3for 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[i,k];
end
else
begin
d[i,j]:=d[i,j];
p[i,j]:=p[i,j];
end;
inc(k);
end;
end;
procedure output;
var i,j:integer;
begin
assign(f,'floydwar.out');rewrite(f); for i:=1 to n do
begin
for j:=1 to n do
write(f,d[i,j]:10);
writeln(f);
end;
writeln(f);
for i:=1 to n do
begin
for j:=1 to n do
write(f,p[i,j]:10);
writeln(f);
end;
close(f);
end;
BEGIN
clrscr;
Trang 4input;
init;
floydwar;
output;
write('xem ket qua trong file:floydwar.out'); readln;
END
File vào ví dụ: (FLOYDWAR.INP)
4 7
1 2 7
1 3 5
2 3 7
2 4 6
3 4 11
4 1 4
4 2 1
File ra tương ứng: (FLOYDWAR.OUT)
17 7 5 13
10 7 7 6
15 12 19 11
4 1 8 7
2 2 3 2
4 4 3 4
4 4 4 4
1 2 2 2