algorithm - 所有对最短路径与动态规划

Question

全部，

我正在阅读所有对最短路径和矩阵乘法之间的关系。

Consider the multiplication of the weighted adjacency matrix with itself - except, in this case, we replace the multiplication operation in matrix multiplication by addition, and the addition operation by minimization. Notice that the product of weighted adjacency matrix with itself returns a matrix that contains shortest paths of length 2 between any pair of nodes.

从这个论证可以得出，A 的 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等人的算法导论一书中，提到如下:

实际的最短路径权重 delta(i, j) 是多少？如果图中不包含负权重环，则所有最短路径都是简单路径，因此最多包含 n - 1 条边。从顶点 i 到顶点 j 的路径具有多于 n - 1 条边，其权重不能小于从 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. Eq 2 并非直接来自 Eq1。 Eq 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) 处停止计算，并确保您在 所有 路径中拥有 所有 长度的最小路径。 (这是显而易见的，但教科书在这里严格是有道理的……)