Is Dijkstra's algorithm the most suitable for finding the shortest distance between two nodes, where all of the paths in the graph are equal to 1.
If not what is a more time efficient way of implementing this?
-
2Why not just breadth first search?Mark– Mark2024-04-25 19:44:31 +00:00Commented Apr 25, 2024 at 19:44
-
Forgot to mention the graph is weighted, think of it as airports for the nodes and flight duration for the paths.Georgi Traykov– Georgi Traykov2024-04-25 19:50:31 +00:00Commented Apr 25, 2024 at 19:50
-
"where all of the paths in the graph are equal to 1" This is not a weighted graph. Which is it, weighted or unweighted?beaker– beaker2024-04-25 20:02:58 +00:00Commented Apr 25, 2024 at 20:02
-
When your graph is unweighted (all edge weights are 1), then Dijkstra's algorithm reduces to a standard breadth-first search algorithm.trincot– trincot2024-04-25 21:13:22 +00:00Commented Apr 25, 2024 at 21:13
-
my bad, it is unweightedGeorgi Traykov– Georgi Traykov2024-04-26 04:46:05 +00:00Commented Apr 26, 2024 at 4:46
Add a comment
|
2 Answers
When your graph has edge weights that are the same positive constant, then your graph is actually unweighted. Dijkstra's algorithm is intended for weighted graphs. If you apply it to unweighted graphs, then the priority queue used in that algorithm can be replaced by a FIFO queue. This turns the algorithm into a standard breadth-first search.
This is also what is stated in the Wikipedia entry on Dijkstra's algorithm:
Breadth-first search can be viewed as a special-case of Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue.
Comments
a* can be faster. But this question is mostly a dupe of others.
