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

Question

所有，

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

考虑加权邻接矩阵与 本身 - 除了在这种情况下，我们替换乘法运算 在矩阵乘法和加法中，以及加法运算 最小化。请注意，加权邻接矩阵的乘积 with 本身返回一个包含长度为 2 的最短路径的矩阵 任意一对节点之间。

从这个论证可以得出，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) power (n-1) = (i,j) power (n) = (i,j) power (n+1) ) = ...

问题 3：在上面的等式中，作者如何得到 n, n+1 条边，因为我们最多有 n-1 条边，以及上面的作业是如何工作的？

谢谢！

Answer 1

1. n 与 n-1 只是一个不幸的变量名称选择。他应该使用不同的字母来更清楚。

   A^1 的最短路径长度可达 1（简单地说）
   A^2 的最短路径长度可达 2
   A^k 具有长度可达 k 的最短路径
   

2. 方程 2 并非直接来自方程 1。方程 2 只是第一个方程的第二项。我认为这是一个格式或复制粘贴错误（我无法检查 - 您的 ppt 链接已损坏）

3. 作者只是明确指出，向路径：

   A^(n-1), //长度为tp(n-1)的最短路径
   等于A^n //长度为tp(n)的最短路径
   等于A^(n+1) //长度为tp(n+1)的最短路径
   ...
   

   这只是为了让您可以安全地在 (n-1) 处停止计算，并确保您拥有所有长度的所有路径中的最小路径。 （这很明显，但教科书在这里严格要求是有道理的......）

Answer 2

在图中，路径中的两个节点之间最多有 n-1 条边，作者在什么基础上讨论长度为“n”的路径？

您混淆了正在讨论的多种度量：

• A^n 表示顶点之间长度n 的“最短路径”（按权重）。
• “两个节点之间最多有 n-1 条边”——我认为在这种情况下，您将 n 视为图形的大小。

该图可能有数百个顶点，但邻接矩阵 A^3 显示长度为 3 的最短路径。不同的 n 度量。