动态规划求解所有点对之间的最短路径

Question

3

大家好，

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

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

由此可见，A的幂次方包含所有最短路径。

问题1：

我的问题是，在图形中，两个节点之间最多会有n-1条边连接成路径，根据什么依据作者讨论“n”长度的路径？

以下是幻灯片

第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个边缘，并且上述赋值如何起作用？

谢谢！

- venkysmarty

2个回答

0

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

你混淆了多个讨论的措施：

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

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

- sarnold

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hugomg · Accepted Answer

The n vs n-1 is just an unfortunate variable name choice. He should have used a different letter instead to be more clear.

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

Eq 2 does not directly come from Eq1. Eq 2 is just the second term from the first equation. I presume this is a formatting or copy-paste error (I can't check - your ppt link is broken)
The author is just explicitly pointing out that you have nothing to gain by adding more then n-1 edges to the path:
```
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)
...
```
This is just so that you can safely stop your computations at (n-1) and be sure that you have the minimum paths among all paths of all lengths. (This is kind of obvious but the textbook has a point in being strict here...)