Finding shortest path for equal weighted graph

Question

I have a graph which is of equal weights. How can I find the shortest path? We can use DijKstra's Algorithm and find the shortest path. I think backtracking will be used in this case. But is there any other way to find the shortest path optimally as graph is of equal weights?

Answer 1

BFS is the best way to get the shortest path from one node to another...it first finds all the nodes at distance 1 then 2 and so on

Answer 2

I think the bfs algorithm is best for graph with equal weights to solve the shortest-path. I think also Bfs is the best algorithm in a graph satisfy triangle inequality, like a planar graph.

Answer 3

I don't entirely understand what you are trying to say but to find shortest path as an alternate to DijKstra's algorithm look up A* ( pronounced a star ). It is a similar algorithm only it adapts a heuristic to reduce the number of checks it need to do. DijKstra's is almost like A* with a heuristic of zero which is far off from the true heuristic. The closer you can predict the heuristic the quicker the algorithm.

Answer 4

You can also use Floyd-Warshall's algorithms to calculate the shortest paths between every pair of nodes in the graph. If your graph is small and you will be doing a lot of querying this is the way to go. The algorithm is fairly simple:

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]);
         }
      }
   }
}

The time complexity is O(n^3), where n is the number of nodes.

Otherwise, use the BFS.