<分区>
图G是一个无向图，其所有边的权重都相同。 u,v 是 2 个给定的顶点，如何求图 G 中 u 和 v 之间的最短路径数 O(|V|)?
|V|表示G中的顶点数。
<分区>
图G是一个无向图，其所有边的权重都相同。 u,v 是 2 个给定的顶点，如何求图 G 中 u 和 v 之间的最短路径数 O(|V|)?
|V|表示G中的顶点数。
最佳答案
因为 Dijkstra 是贪婪的，并且不断地按递增的顺序消耗路径。当稍后发现负权重时，这可能意味着较早找到的路径不再是最短路径，因此 Dijkstra 失败。
例子:
A -> B (5)
A -> C (5)
C -> B (-10)
Dijkstra 会发现 A->B (5) 是从 A 到 B 的最短路径，但实际上，最短路径将是 A-> C -> B (-5)
关于algorithm - 如何在 O(|V|) 的无向图中找到 u 和 v 之间的所有最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27589698/