動態編程的所有最短路徑對

Question

全部，

我正在閱讀有關所有對最短路徑和矩陣乘法之間的關係。

考慮加權相鄰矩陣的乘法與 本身 - 除非，在這種情況下，我們通過添加替換矩陣乘法的乘法運算 ，並通過 最小化的加法運算。請注意，加權鄰接矩陣 與其自身的乘積返回一個矩陣，其中包含任何節點對之間的最短路徑長度爲2 。

從這個說法可以看出，對於n的冪包含所有的最短路徑。

的第1題：

我的問題是，在圖中，我們將在兩個節點之間的路徑最n-1個邊緣有，憑什麼是筆者長度的「n」的路徑的探討？

以下幻燈片

www.infosun.fim.uni-passau.de/br/lehrstuhl/.../Westerheide2.PPT

在滑動件10它被提及如下。

dij(1) = cij 

dij(m) = min (dij(m-1), min1≤k≤n {dik(m-1) + ckj}) --> Eq 1 
     = min1≤k≤n {dik(m-1) + ckj} ------------------> Eq 2 

問題2：如何筆者從公式1.介紹算法得出公式2

在Cormen等人的書，它被提及如下：

有什麼實際的最短路徑權重增量（i，j）？如果圖形不包含負重循環，則所有最短路徑都很簡單，因此最多包含n-1個邊。從頂點i到具有多於n-1個邊的頂點j的路徑不能比從i到j的最短路徑具有更小的權重。因此，實際的最短路徑權重爲：

delta（i，j）= d（i，j）功率（n-1）=（i，j）功率（n）=（i，j）功率（n + 1）= ...

問題3：在上面的等式中，作者是如何帶有n，n + 1個邊的，至多我們有n-1個，還有上面的賦值是如何工作的？

謝謝！

Answer 1

1. n對n-1只是一個不幸的變量名稱的選擇。他應該使用不同的字母來代替，以便更清楚。

   A^1 has the shortest paths of length up to 1 (trivially) 
   A^2 has the shortest paths of length up to 2 
   A^k has the shortest paths of length up to k 
   

2. 等式2不直接來自等式1。公式2只是第一個等式的第二項。我認爲這是一個格式化或複製粘貼錯誤（我無法檢查 - 你的ppt鏈接被破壞）

3. 作者只是明確指出，通過添加更多的n-1邊到路徑：

   A^(n-1),   //the shortest paths of length up tp (n-1) 
   is equal to A^n  //the shortest paths of length up tp (n) 
   is equal to A^(n+1) //the shortest paths of length up tp (n+1) 
   ... 
   

   這僅僅是讓你可以放心地在（N-1）停止你的計算，並確保你有中的所有長度所有最小路徑路徑。 （這是顯而易見的，但是教科書在這裏有點嚴格...）

Answer 2

在圖中，我們將在一個路徑中的兩個節點之間具有最接近的n-1個邊，基於作者正在討論的長度爲「n」的路徑？頂點之間的長度Ñ的

• 甲^ N代表 「最短路徑」（以重量計）：

你混淆正在討論的多種措施。

「最多n-1兩個節點之間的邊緣」 - 我推測在這種情況下，您正在考慮n作爲圖的大小。

該圖可能有數百個頂點，但你的鄰接矩陣a^3顯示長度3.不同ň措施的最短路徑。