设 path[i][j] 记录i到j的最短路径中j的前驱顶点。

初始化： i到j有边，则 path[i][j]:=i; path[j][i]:=j;

for k:=1 to n do

    for i:=1 to n do

        for j:=1 to n do 

            if d[i][k]+d[k][j]<d[i][j] then

            begin

                d[i][j]:=d[i][k]+d[k][j];

                path[i][j]:=path[k][j];

            end;