想請教有關於 求最短路徑技巧 relaxtion 後的相關性質
我是在這個網站中學習的
http://alrightchiu.github.io/SecondRound/shortest-pathintrojian-jie.html
不過我想問這個網站中所介紹的 ”convergence property“, 如果說演算法是為了尋求最短路徑, 而這個性質卻已經假設 :
假定Graph上存在從vertex(X)指向vertex(Y)之edge(X,Y),並且從起點vertex走到vertex(Y)之最短路徑包含這條edge。
那麼這個性質不就是要等已經得到最短路徑後才有其功用嗎? 換句話說,如果我們尚未知道最短路徑,又如何從這個性質去套用於 “Path-relaxation property”呢。 也就是在網站上所寫的這段 :
在對edge(v1,v2)進行Relax()之前,只要已經對edge(v0,v1)進行過Relax(),那麼,不管還有對其餘哪一條edge進行Relax(),distance[2]必定會等於δ(0,2) ,因為Convergence property。
令我所困擾的是這兩個性質似乎有關, 我卻無法理解 ”convergence property 對於這章節所真正要表達的意涵。
因而導致我也無法思考 “Path-relaxation property” 的正確性。
另外還有一個小問題是關於 :
為何 Bellman-Ford Algorithm 對於每一次 ”relax” 所有 edge 的迴圈中必定可以產生一段最短路徑“邊”。
不過為何要讓迴圈執行 |V| - 1次我已經明白。 我也理解 Dijkstra’s Algorithm 在每一次找一個 在 S子集外 的 V, 其最小的d[v] (v屬於V),而
每一次找到的最小d[v]都會增加 Dijkstra spanning tree。
http://alrightchiu.github.io/SecondRound/single-source-shortest-pathbellman-ford-algorithm.html — Bellman and Ford
希望可以大大可以幫助我 謝謝