Re: [問題] 小題目：各點之間的最小連結步數

看板Fortran作者mantour (朱子)時間15年前 (2009/12/09 20:02)推噓1(1推 0噓 1→)

留言2則, 1人參與討論串6/6 (看更多)

還是用符號來說明一下這個演算法的精神好了以下 Vi -> Vj 表示 Vi -> Vj 的直接連結而 Vi -> {Va, Vb } -> Vj 表示 Vi -> Vj 經過或不經Va,Vb的所有走法中，最短的走法也就是 Vi -> Vj Vi -> Va -> Vj Vi -> Vb -> Vj Vi -> Va ->Vb ->Vj Vi -> Vb ->Va ->Vj 這五種組合中，路程最短的那一個走法首先一開始 D(i,j) = Vi -> Vj 等到 k =1 跑完 D(i,j) = Vi -> {V1} -> Vj 等到 k=2 跑完 D(i,j) = Vi -> {V1,V2} -> Vj 等到 k=3 跑完 D(i,j) = Vi -> {V1,V2,V3} -> Vj ...... 等到 k=n跑完 D(i,j) = Vi -> {V1,V2,...,Vn} -> Vj ======================================== 如果你反過來跑先跑 k=n D(i,j) = Vi -> {Vn} -> Vj k=n-1 D(i,j) = Vi -> {Vn , V_(n-1)} -> Vj ...... k=1 D(i,j) = Vi -> {Vn, ... , V2, V1} -> Vj 所以只要從k=1到k=n全部跑完一遍最後的結果都會是一樣的 By the way 如果你不只要找最短路距離，還希望能記下最短路徑的話可以建一個linked list的陣列來存放相對應的路徑不過fortran裡的實作方法我不太熟就是了其他相關的最短路徑演算法可以參考wikipedia Dijkstra's algorithm solves the single-pair, single-source, and single-destination shortest path problems. Bellman-Ford algorithm solves single source problem if edge weights may be negative. A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search. Floyd-Warshall algorithm solves all pairs shortest paths. Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd-Warshall on sparse graphs. Perturbation theory finds (at worst) the locally shortest path. ※ 引述《yin0416 (冷色鉛筆)》之銘言： : 關於最外層迴圈的順序問題，我的發現是， : 找出正確路徑長的順序不只一種， : 以　V4--V5--V1--V2--V3 為例，找出V4到V3的距離， : K由1~5依序代入的話， : A.會先找出V5--V1--V2的長度， : B.再找出V5--(V1)--V2--V3， : C.最後找出V4--(V5)--(V1)--V2--V3 : 找出的順序是A-->B-->C， : 但如果將順序反過來的話，即C-->B-->A時， : 是無法找出正確路徑長的， : 現在我們將K由5~1依次代入， : D.先找出V4--V5--V1 : E.再找出V1--V2--V3 : F.最後再找V4--(V5)--V1--(V2)--V3 : 結論，不只一種拼出路徑長的方式！ : 謝謝各位的耐心觀看　＞＿＜ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.213.158 ※ 編輯: mantour 來自: 140.112.213.158 (12/09 20:16) ※ 編輯: mantour 來自: 140.112.213.158 (12/09 20:18)