给定一个顶点的所有最短路径

Question

3

给定一个有向图G=(V,E)，以及一个边权重函数w : E -> R+（仅针对图中的正权边），我需要找出从每个顶点v到给定顶点k的所有最短路径。

我考虑将图中的边反转，然后从顶点k运行Dijkstra's algorithm。我想知道，从k到v1的最短路径p是否实际上是在反转边之前的原始图中从v1到k的最短路径。

如果有人能解释一下为什么会或者不会发生这种情况，我将不胜感激。

提前感谢。

- user975343

3

目前我没有正式的东西，但是你的想法应该不错。考虑如果图是无向的会发生什么：两条路径显然是相同的。你所建议的基本上导致了一个无向图，所以两者是相同的。 - IVlad

这也是我考虑过的，但我想知道是否存在某种情况，它不会发生。 - user975343

这个的有效性直接来自于通过反转边缘所产生的对称性。你没问题。 - G. Bach

对于有向图的每个语句，都存在一个关于反转所有边缘的图的对偶语句。你的例子就是其中之一。 - n. m.

有些事情很难证明，因为它们太显而易见了。（我记得 Knuth 对此曾经发表过一篇不错的抨击文章。）这就是其中之一。 - Sneftel

1个回答

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

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

- gms7777 · Accepted Answer

假设在图G中，对于一个顶点v，到顶点k的最短路径长度为m。你需要知道以下两件事：
1. 在反向图G*中，从k到v的路径长度为m。
2. 在反向图G*中，从k到v的所有路径长度都不小于m。

在开始之前，我们可以先相信一件事：
引理1：如果你有一条从顶点v到顶点w的有向路径，并且你将路径上的每条边都反向，那么你就得到了一条从顶点w到顶点v的路径。这个引理是可以证明的，但我认为这是相当常识的。如果你想要我证明，我可以证明它。

对于第一点：考虑在G中从v到k的路径，由m条边组成。如果你反转这些边，你就得到了一条从k到v的长度为m的路径（根据引理1）。

对于第二点：假设在反向图G*中存在一条从k到v的长度为n<m的路径。如果你反转这条路径，那么就会得到一条长度为n的从v到k的路径（根据引理1）。这意味着在原始图中存在一条比m更短的从v到k的路径，这与路径长度为m是最短路径的说法相矛盾。