给定一个有向图 G=(V,E) 和一个权重函数 w : E - > R+（只有图中边的正权重），我需要找到从 V 中的每个顶点 v 到给定顶点的所有最短路径ķ。
我考虑过反转图中的边，然后从顶点 k运行Dijkstra 算法。我想知道从 k 到 v1 的最短路径 p 是否实际上是原始图中从 v1 到 k 的最短路径（在反转边之前）。
如果有人能解释它是否发生以及为什么不会发生，我将不胜感激。
提前致谢。
user975343
问问题
597 次
1 回答
2
（这不会是世界上最正式的证明，但希望它足以说服自己）。
假设对于顶点v，在图G中，从v到k的最短路径的长度为m。您想知道的两件事是：
1. 在反向图 G* 中，有一条从k到v的长度为m的路径。
2. 在反向图 G* 中，没有从k到v的路径比m短。
在我开始之前，我们可以相信一件事：
引理 1：如果你有一条从顶点v到顶点w的有向路径，并且你反转路径上的每条边，那么你就有一条从顶点w到顶点v的路径。这是可以证明的，但我认为这是相当常识的。如果你要我证明，我会证明的。
对于第 1 点：考虑G中从v到k的路径，该路径由m条边组成。如果你反转这些边中的每一个，你将有一条从k到v的路径，长度为m（由引理 1）。
对于第 2 点：假设在反向图 G* 中存在一条路径，从k到v，长度为n < m。如果你反转这条路径，那么有一条从v到k的长度为n的路径（引理 1）。这意味着在原始图中有一条从v到k的路径比m短，这与长度为m的路径最短的说法相矛盾。
于 2013-11-25T15:50:41.690 回答