CODEWITHSUNDEEP
graph-algorithmshortest-path
BrockenDuck
BrockenDuck

Reputation: 220

Dijkstra's Algorithm, how to choose next node when they have the same length

in Dijkstra's Algorithm (to find the shortest path), when you have analyzed all the paths going from the current node that were not visited, and found their tentative distance. You have to select the next node to go to and this is done by selecting the one with the shortest tentative distance. This is pretty easy, except when there are more than one paths with the same length. For example in this graph :

enter image description here

If we try to go from node 0 to node 5, there are two paths, first we go to node 4 and then we have to choose between 6 and 8. This is complicated and the algorithm would choose between the two paths of length 10.

I see 3 options :

I really don't know how to proceed, thank you for reading.

(Cross posted on theoretical computer science stack exchange)

Upvotes: 0

Views: 1351

Answers (1)

Piotr Żak
Piotr Żak

Reputation: 2132

This particular case isn't very complicated.

It depends on the analysed depth:

The only start possibility:

0 - 4(cost:10)

Now there is a decision point - with 2 possible ways.

The I deepth level is identical in term of cost:

  • 0 - 4(c:10) - 6 (c:10)
  • 0 - 4(c:10) - 8 (c:10)

So let's see the II depth level

  • 0 - 4(c:10) - 6 (c:10) - 3 (c:5)
  • 0 - 4(c:10) - 8 (c:10) - 5 (c:5)

You are on finiish so - the second way is the most optimized in this environment (if, however, the road does not end - the algorithm analyzes further) and chooses the most optimal decision based on several depths.

Of course - here is an implementation (it's more complex - because U need to take care about all possible cases/scenarios and affordances):

Dijkstra's algorithm in python https://www.bogotobogo.com/python/python_Dijkstras_Shortest_Path_Algorithm.php

Upvotes: 2

Related Questions