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ậ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)
Đỉnh đầu
Đỉnh
cuối
Trọng số
x
1
y
1
w
1
x
2
y
2
w
2
… … …

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
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[i,k];
end
else
begin
d[i,j]:=d[i,j];
p[i,j]:=p[i,j];
end;
inc(k);

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