1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.