Search code examples
algorithmshortest-pathdijkstra

How does Djikstra's Algorithm handle cornering?

Consider this graph

enter image description here

If we consider A to be the source node and C to be the destination, Dijkstra’s algorithm will first move to D as it is the shorter path and then begin looking for nodes connecting to D.

Now consider the same graph but without edges from D to B and from D to E.

When the current node is A (initial state), The algorithm finds that the shorter path between B and D is D, So it moves to D. However, now that there are no edges remaining from D and A is already explored, Wouldn't the algorithm get stuck at D. Wouldn't it be better if we decided to move to be B instead of D while at A?

How does the algorithm handle this situation? Thanks

Solution

  • The algorithm is not physically moving in the graph. It's enqueuing nodes that it sees into a priority queue. This allows it to "jump" around arbitrarily, to whichever node has the next shortest path.