Dijkstra算法当所有边的权重相同时

Question

如果在给定的图中，所有边的权重都相同，那么Dijkstra算法是否仍能找到两个顶点间的最短路径呢？ 谢谢！

- sinou

Answer 1

是的，Dijkstra算法可以在所有边权重相同时找到最短路径。Dijkstra的时间复杂度为O((V+E)logV)。但实际上，你应该选择BFS算法来完成相同的任务，因为BFS的时间复杂度为O(V+E)，所以BFS在渐近意义下比Dijkstra更快。

- Tanmoy Banerjee

---

这个答案中的时间复杂度分析是错误的。如果使用合理的实现运行迪杰斯特拉算法，它也将以 O(V+E) 的时间运行。实际上，无论是迪杰斯特拉还是 BFS 都可以在 O(E) 的时间内运行，以找到两个给定顶点之间的最短路径。 - burnabyRails

Answer 2

是的，它可以解决问题。但你可能需要看一下广度优先搜索，它可以解决你提到的情况。 要找到路径，你可以编写一个递归函数，从目标节点开始，标记距离为n，并移动到一个标记距离为n-1的邻居节点之一。

- germangb