floyd.m

MATHEMATICA 程序 最短路径算法

d = Flatten[Import["c:\\2.xls"], 1];
floyd[d0_List, dian1_, dian2_] := 
Module[{d = d0, n, i, j, k, r, t, lujing}(*d0为邻接矩阵,
dian1.dian2为要求得的最短路径两点*),
n = Length[d];
r = DiagonalMatrix[Table[0, {i, n}]];
For[i = 1, i <= n, i++,
   For[j = 1, j <= n, j++,
       r[[i, j]] = j;
     ];
   ];
For[k = 1, k <= n, k++,
   For[i = 1, i <= n, i++,
     For[j = 1, j <= n, j++,
       If[d[[i, k]] + d[[k, j]] < d[[i, j]], 
         d[[i, j]] = d[[i, k]] + d[[k, j]]; r[[i, j]] = r[[i, k]];];
       ];
     ];
   ];(*d 为最小权值，r为临近链接点*)
Print["最小权值为：", d[[dian1, dian2]]];
lujing = {dian1};
Print ["Path:", lujing[[1]] ];
t = r[[dian1, dian2]];
While[t != dian2, t = r[[t, dian2]]; Print ["---->", t]; 
   AppendTo[lujing, t]];
]

floyd[d, 1, 6]

最小权值为：80.

Path:1

---->3

---->5

---->6

(*2.xls：[e-mail]*)