iT邦幫忙

0

Shortest Path 性質

想請教有關於 求最短路徑技巧 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

希望可以大大可以幫助我 謝謝

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友回答

立即登入回答