6

我有一个权重相等的图表。如何找到最短路径？我们可以使用DijKstra's Algorithm并找到最短路径。我认为在这种情况下将使用回溯。但是，由于图的权重相等，还有其他方法可以最佳地找到最短路径吗？

4

4 回答 4

15

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

于 2013-06-13T11:29:06.233 回答
3

我认为 bfs 算法最适合具有相同权重的图来解决最短路径。我认为 Bfs 也是图中满足三角形不等式的最佳算法，例如平面图。

于 2013-06-13T11:29:16.630 回答
1

我不完全明白你想说什么，但要找到最短路径作为 DijKstra 算法查找 A* 的替代方法（发音为星号）。它是一种类似的算法，只是它采用启发式算法来减少需要执行的检查次数。DijKstra 几乎像 A* 一样，启发式为零，与真正的启发式相去甚远。您可以越接近地预测启发式算法，算法就越快。

于 2013-06-13T11:30:16.760 回答
1

您还可以使用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。

于 2013-06-13T11:38:56.070 回答