[Math] Is Dijkstra’s algorithm possible with graphs containing dead ends

algorithmsgraph theory

I'm struggling to get my head around this specific example using Dijkstra's algorithm. Basically, the algorithm (or my possible incorrect interpretation thereof) is getting stuck in a dead end and is not able to reach the end node.

Say we try to find the shortest distance between node A and node G. Starting at A, the closest node is C with a weighting of 3. After assigning 3 to the permanent value of node C, we look at its relevant connections. The total current weightings are as follows:

A -> E = 14
C -> B = 8
C -> D = 19
C -> E = 12

Since node B has the shortest total weighting of 8, we assign its permanent value and move on. Now we've reached a dead end, and I'm really not sure how to continue from here.

An example of a graph with a dead end

As the title suggests, my question is whether it is possible to move on from the dead end and continue the traversal somehow. If so, how?

Thanks in advance
Chris

Best Answer

No you have not reached a dead end. The set of vertices whose connections you need to consider for the next step is ( A, B, C). True, one of them (B) has no further connections but the other two (A,C) do. The edges that need to be considered for the next step are CD, CE and AE of which you choose CE (since CE has the smallest distance of 9) and add E to the set. The process is repeated again.

Related Question