Menu
In Dijkstra's algorithm what should I do if there are two or more nodes with minimal weights at a point in the algorithm?
In wikipedia: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm at step no. 6, it says
"Set the unvisited node marked with the smallest tentative distance as the next 'current node' and go back to step 3."
What if there are two or more nodes with "smallest tentative distance".
Can anyone help me with the algorithm?
478
Dijkstra's algorithm solves the shortest-path problem for any weighted, directed graph with non-negative weights. It can handle graphs consisting of cycles, but negative weights will cause this algorithm to produce incorrect results.
Dijkstra itself has no problem with 0 weight, per definition of the algorithm. It only gets problematic with negative weights. Since in every round Dijkstra will settle a node. If you later find a negative weighted edge, this could lead to a shorter path to that settled node.
One common way to find the shortest path in a weighted graph is using Dijkstra's Algorithm. Dijkstra's algorithm finds the shortest path between two vertices in a graph. It can also be used to generate a Shortest Path Tree - which will be the shortest path to all vertices in the graph (from a given source vertex).
Just pick either. Unless you have another heuristic to work with, you can't tell which would be better to pick.
Think about sorting some elements into an array:
9 6 3 3 8
sorted with lowest first is
3 3 6 8 9
If you were to query that array to determine the lowest, the answer is 3. Which 3 doesn't matter.
Similarly if you were to have some more information. Say for example that those ints were actually floats and were sorted by their integer parts. You might end up with the array:
3.2 3.1 6.0 8.5 9.2
Here you have another heuristic to work with, you can check the decimal part too, and you can determine that 3.1 is the lowest.
185
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
