在等权图中寻找最短路径

Question

我有一个等权重的图，如何找到最短路径？ 我们可以使用 DijKstra算法 来找到最短路径。我认为在这种情况下将使用回溯。但是，由于图的权重相等，是否有其他方法可以更优地找到最短路径？

- Vaibs

Answer 1

BFS是从一个节点到另一个节点获取最短路径的最佳方法...它首先找到距离1的所有节点，然后是距离2等等

- sethi

---

+1 最简单和最快的方法。虽然这可能被认为是常识（而且谷歌是你的朋友），但你可以补充说明BFS代表广度优先搜索 :) - Vincent van der Weele

我仔细阅读了BFS算法并且很快就理解了。谢谢，这对我很有帮助。我参考了http://courses.engr.illinois.edu/cs473/sp2011/Lectures/03_class.pdf。 - Vaibs

Answer 2

我认为在等权图中解决最短路径问题，BFS算法是最好的选择。同时，如果一个图满足三角不等式，比如平面图，我认为BFS也是最好的算法。

- Micromega

Answer 3

你还可以使用 Floyd-Warshall 算法来计算图中每对节点之间的最短路径。如果你的图比较小，而且需要进行大量查询，那么这种方法是可行的。该算法相当简单：

public static void floydwarshall(int[][] graph){
   for(int k=0; k<graph.length; k++){
      for(int i=0; i<graph.length; i++){
         for(int j=0; j<graph.length; j++){
            graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
         }
      }
   }
}

时间复杂度为O(n^3)，其中n是节点数。

否则，使用BFS。

- darijan

Answer 4

我不完全理解你想说什么，但如果要寻找最短路径作为 DijKstra 算法的替代方案，请查阅 A*（发音为 a star）。它是一种类似的算法，只是它采用启发式来减少需要检查的数量。DijKstra 几乎就像带有零启发式的 A*，这与真实启发式相去甚远。您可以预测启发式越接近，算法运行得越快。

- PhobicHD