3

全部，

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

考虑加权邻接矩阵与其自身的乘法 - 除了在这种情况下，我们将矩阵乘法中的乘法运算替换为加法，并将加法运算替换为最小化。请注意，加权邻接矩阵与其自身的乘积会返回一个矩阵，该矩阵包含任何节点对之间长度为 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：作者如何从 Eq 1 得出 Eq 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 条边，以及上面的分配是如何工作的？

谢谢！

4

2 回答 2

4

  1. n vs 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。方程 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) 处停止计算，并确保您拥有所有长度的所有路径中的最小路径。（这很明显，但教科书在这里有严格的意义......）

于 2011-12-05T13:07:19.683 回答
0

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

您混淆了正在讨论的多项措施：

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

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

于 2011-12-05T12:35:12.890 回答