给定顶点的所有最短路径

2018-06-12 07:57:39

给定一个有向图G =（V，E）和一个权重函数w：E - > R +（图中边只有正权重），我需要找到V中每个顶点v到给定顶点的所有最短路径ķ。

我曾想过在图中反转边缘，然后从顶点k运行Dijkstra算法。我想知道从k到v1的最短路径p实际上是从原始图中（在倒转边之前）从v1到k的最短路径。

如果有人能解释是否以及为什么它会发生，我会很感激。

提前致谢。

（这不是世界上最正式的证据，但希望它足以说服你自己）。

假设对于顶点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的路径最短的说法相矛盾。

链接地址: http://www.djcxy.com/p/35281.html