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

如果给定图中所有边具有相同权重，Dijkstra算法是否仍然会找到2个顶点之间的最短路径？谢谢！当所有边具有相同权重时，Dijkstra算法

2014-01-24 sinou

是Dijkstra算法的neightbour节点之一甚至可以找到最短路径当所有边缘具有相同的重量时。 dijkstra的时间复杂度为O（（V + E）logV）。因为BFS的时间复杂度为O（V + E），所以BFS算法比dijkstra渐近地快。

2014-02-04 10:10:43 tanmoy

是的，但你可能想看看Breadth-first search，这解决了你所指的情况。要查找路径，你可以做一个递归函数启动与标记的距离n命运的节点，并移动到与标记的距离N-1

2014-01-27 13:00:27 germangb

回答