3
votes

If all edges had the same weight in a given graph, will Dijkstra's algorithm still find the shortest path between 2 vertices? Thanks!

2

2 Answers

5
votes

Yes dijkstra algorithm can find the shortest path even when all edges have the same weight. dijkstra has time complexity O((V+E)logV).Instead you should choose BFS algorithm to do the same thing,because BFS has time complexity O(V+E),so BFS is asymptotically faster than dijkstra.

2
votes

Yes it would, But you might want to take a look at Breadth-first search, wich solves the case you are refering to. To find the path, you can make a recursive function that starts in the destiny node with flagged distance n, and moves to one of the neightbour nodes with flagged distance n-1