Thuật toán FLOYD - Đường đi ngắn nhất giữa mọi cặp đỉnh

Cho đơn đồ thị có hướng, có trọng số G=(V,E) với n đỉnh và m cạnh, Ma trận trọng số C[u,v]. Bài toán đặt ra là tính tất cả các d(u,v) là khoảng cách nhỏ nhất từ u đến v.

Ta sử dụng thuật toán FLOYD để giải quyết bài toán này. Từ ma trận trọng số ban đầu C, ta tính lại các C[u,v] thành đường đi ngắn nhất từ u đến v theo công thức:
C[u,v] := min (C[u,v], C[u,k] + C[k,v]) với mọi đỉnh k xét từ 1 đến n.

Tức là: Nếu đường đi đang có từ u đến v dài hơn đường đi từ u đến k cộng với đường đi từ k đến v thì ta ghi nhận lại đường đi ngắn nhất (hiện có) là đường đi qua k.

for k:=1 to n do
for u:=1 to n do
for v:=1 to n do
c[u,v] := min ( c[u,v] , c[u,k] + c[k,v] );

Chứng minh:
Gọi D[k,u,v] là độ dài đường đi ngắn nhất từ u đến v mà chỉ đi qua các đỉnh trung gian thuộc tập {1,2,…,k}. Rõ ràng ban đầu, khi k=0 thì D[0,u,v] =C[u,v] (đường đi trực tiếp).
Giả sử đã tính được các D[k-1,u,v], D[k,u,v] sẽ được tính bằng cách:

* Không đi qua đỉnh k, tức là chỉ sử dụng các đỉnh trung gian từ 1 đến k-1 thì
D[k,u,v] := D[k-1,u,v];
* Đi qua đỉnh k, khi đó đường đi ngắn nhất từ u đến v sẽ là nối của hai đường, một đường từ u đến k, một từ k đến v, và các đường con này chỉ đi qua các đỉnh trung gian từ 1..k-1
D[k,u,v] := min ( D[k-1,u,k] + D[k-1,k,v] )


Cài đặt :

Code:

program Shortest_Path_by_Floyd;
const
max = 100;
maxC = 10000;
var
c: array[1..max, 1..max] of Integer;
Trace: array[1..max, 1..max] of Integer;
n, S, F: Integer;

procedure LoadGraph;
var
i, m: Integer;
u, v: Integer;
begin
Readln(n, m, S, F);
for u := 1 to n do
for v := 1 to n do
if u = v then c[u, v] := 0 else c[u, v] := maxC;
for i := 1 to m do Readln(u, v, c[u, v]);
end;

procedure Floyd;
var
k, u, v: Integer;
begin
for u := 1 to n do
for v := 1 to n do Trace[u, v] := v;
for k := 1 to n do
for u := 1 to n do
for v := 1 to n do
if c[u, v] > c[u, k] + c[k, v] then
begin
c[u, v] := c[u, k] + c[k, v];
Trace[u, v] := Trace[u, k];
end;
end;

procedure PrintResult;
begin
if c[S, F] = maxC
then Writeln('Not found any path from ', S, ' to ', F)
else
begin
Writeln('Distance from ', S, ' to ', F, ': ', c[S, F]);
repeat
Write(S, '->');
S := Trace[S, F];
until S = F;
Writeln(F);
end;
end;

begin
Assign(Input, 'MINPATH.INP'); Reset(Input);
Assign(Output, 'MINPATH.OUT'); Rewrite(Output);
LoadGraph;
Floyd;
PrintResult;
Close(Input);
Close(Output);
end.