(* 定義資料 *)
data={{1,2,6.2},{1,3,4.0},{2,3,2.0},{2,4,2.0},{3,4,1.0},{3,5,2.0},{4,6,7.0},{5,4,1.0},{5,6,3.0}}
(* 計算距離矩陣 *)
dist=Table[Infinity,{i,6},{j,6}];(dist[[#[[1]],#[[2]]]]=#[[3]])&/@data
(* 利用ShortestPath計算節點1到6的最短路徑*)
Quiet@ShortestPath[FromAdjacencyMatrix[dist,EdgeWeight],1,6]
(*計算節點1到6的最短距離*)
dist[[#[[1]],#[[2]]]]&/@Flatten[Partition[#,2,1]&/@{Quiet@ShortestPath[FromAdjacencyMatrix[dist,EdgeWeight],1,6]},1]
(*計算節點i到j的最短距離*)
mypath[distmatrix_,start_,end_]:=
Block[{disttemp=distmatrix,i=start,j=end,path,distance},
path={Quiet@ShortestPath[FromAdjacencyMatrix[disttemp,EdgeWeight],i,j]};
distance=disttemp[[#[[1]],#[[2]]]]&/@Flatten[Partition[#,2,1]&/@{Quiet@ShortestPath[
FromAdjacencyMatrix[disttemp,EdgeWeight],i,j]},1];
{Total@distance,path[[1]]}
]
(* Useage：mypath[距離矩陣,起點,終點] *)
mypath[dist, 1, 6]
(*以下計算任意兩點間最短距離*)
(*以下8.0的函數，首先根據距離矩陣定義權重鄰近矩陣*)
g=WeightedAdjacencyGraph[dist,VertexStyle->Yellow,
VertexSize->{1->Small,6->Small},
EdgeLabels->Flatten[(#[[1]]->#[[2]])->ToString[#[[3]]]&/@data]];
(* 利用FindShortestPath計算節點1到6的最短路徑，Mathematica在此提供BellmanFord以及Dijkstra兩種演算法*)
FindShortestPath[g,1,6]
(* 畫出最短路徑 *)
GraphicsRow[HighlightGraph[g,PathGraph[FindShortestPath[g,1,6,Method->ToString[#]],
DirectedEdges->True]]&/@{BellmanFord,Dijkstra}]
使用Mathematica計算最小生成樹
讀者回應 ( 0 意見 )
訂閱發佈留言 (Atom)
發佈留言
Please leave your name and tell me what you thought about this site. Comments, suggestions and views are welcomed.
如果這篇文章對你有幫助，那請留個訊息給我～