还是用符号来说明一下这个演算法的精神好了 以下 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)