CODEWITHSUNDEEP
algorithmgraphgraph-theory
DSPer
DSPer

Reputation: 23

Getting stuck on Djikstra Algorithm

I'm trying to apply Djikstra's algorithm on this graph from my textbook, but I keep getting stuck on vertex A when trying to traverse from G->C. Here is the link to the graph image: LINK

I'll outline my steps below:

  1. I start at the initial vertex(G).

  2. A receives a cost of 6, E receives a cost of 1, H receives a cost of 4 since they are all initially infinity. G is marked as visited.

  3. I go to the neighbor with the shortest cost; in this case its E.

  4. At E, I set the cost of B as 1 + 2 = 3, and the cost of F as 1 + 2 = 3. E is then marked as visited.

  5. I visit the neighbor of E with the lowest cost: This is where I start to get stuck since both B and F have the same cost. Assume that I choose B.
  6. At B, I set the cost of C as 3 + 7 = 10 and the cost of A as 5.
  7. Now A is the neighbor with the lowest cost but accessing it makes me stuck since I can't get out.

I'd really appreciate some suggestions or corrections if I am approaching it wrong.

Upvotes: 2

Views: 82

Answers (2)

Himanshu Patel
Himanshu Patel

Reputation: 99

At step 6 the nodes that have been visited are G, E and B. Now you have to pick the node with the minimum distance value, which is F. So the flaw in step 7 is really the assumption that it has to be a neighbour node.

Continuing from step 7:

  1. Pick F. Update C's distance to 6. Mark F visited.
  2. Pick H. Update D's distance to 6. Mark H visited.
  3. Now pick A. No updates required. Mark A visited.
  4. Pick C or D in any order and mark them visited as well. No updates required here.

Upvotes: 0

hello
hello

Reputation: 11

Since G has already been marked as visited, this node is no longer considered and thus A is also considered, since there are no more possible connections.

Upvotes: 1

Related Questions