Mathematica 教學 Floyd-Warshall演算法求任意兩點間最短距離

定義距離矩陣

dist1=Normal@SparseArray[Flatten[{{1,2}->3,{1,3}->6,{2,3}->2,{2,4}->4,{3,4}->-1,{4,1}->-2,{#,#}->temp&/@Range[4]},1]]//.0->999/.temp->0

定義距離函數

d[i_Integer,j_Integer]:=If[i==j,0,Min[dist[[i,#]]+dist[[#,j]]&/@Range[Length@dist]]]

利用NestList求解

k=0;Row[
Labeled[MatrixForm[#],k++;"Step-"<>ToString@k]&/@
NestWhileList[(dist=#;Table[d[i,j],{i,Length@dist},{j,Length@dist}])&,dist1,
Unequal,All]
]



floyd[x_]:=Module[{n,i,j,k,d},n=Length[x];
d=x;
Do[If[d[[i,j]]>d[[i,k]]+d[[k,j]],
d[[i,j]]=d[[i,k]]+d[[k,j]]],{k,1,n},{i,1,n},{j,1,n}];
d];

floyd[dist1] Tags: Mathematica 教學, Teaching

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有0 意見