CODEWITHSUNDEEP
graphtheory
aerotwelve
aerotwelve

Reputation: 307

Dijkstra's Algorithm: why do I end up stuck in this example?

I've been trying to trace Dijkstra's shortest path algorithm for the following undirected graph:


        (B)
       /   \
      /     \
  6  /       \ 9
    /         \ 
   /           \
  /             \
 (A)- 5 -(C)- 1 -(F)----2----(I)
   \            /
    \          / 
  4  \        / 2
      \      /
       \    /
        \  /
         (D)

For clarification:
(N) will represent nodes, numbers with no formatting will represent weights.
the edge between A and C has a weight of 5, 
the edge between C and F has a weight of 1.

I'll outline my process here:

Since A is my initial node, the algorithm begins here. Since D is the cheaper path, the algorithm traverses to D. A is now marked as visited, meaning we cannot traverse to it again.

At D it is easy to see that we will move to F.

F is where I start having trouble. Since the shortest path will lead me to C, I'm stuck between two visited nodes with no way to get to I. Can anyone help me?

EDIT: Sorry about the graph guys, this question was originally asked from a phone. I'll get that fixed asap.

Upvotes: 4

Views: 2165

Answers (4)

PALEN
PALEN

Reputation: 2876

The way you are working on it is wrong. "At D it is easy to see that we will move to F" that is not true. You first visit D, then C, not F. Take a careful look at the algorithm and what it does.

At first you visit A so you have the following cost: 6 to B, 5 to C, 4 to D and INFINITE for the rest of the nodes.

You first go to D. You now update your cost to go from A to F (passing through D) to 6. Your next node to visit is not D, it is C as it has the lowest cost (5) of all the unvisited nodes. The cost of going from A to F passing through C is 6 which is already the cost you have so there is not need to update.

From there you have a tie of 6 between B and F. Let's say you first go to B, then nothing happens since the shortest path to F is already 6, while passing through B to go to F would cost 15, which is more expensive than the cost you already have so don't update the cost. Then you visit F since it has the lowest cost of all the unvisited nodes. From there you update your path to I which it won't be INFINITE anymore but 8.

As result, your shortest path from A to I is the following sequence: A - D - F - I .

Upvotes: 5

sdcvvc
sdcvvc

Reputation: 25644

Dijkstra's algorithm uses a priority queue. It's not a walk on the graph, and it is possible to visit vertices in order that does not resemble a path. For example, this tree:

A -> B -> C
  \
   > D -> E -> F

with all weights 1 is explored in order A,B,D,C,E,F. Each iteration you visit the vertex with smallest cost and pop it; initially you pop A, the cost of B and D is updated to 1; you visit B, the cost of C is updated to 2; you visit D, the cost of E is updated to 2; you visit E; and finally F.

Upvotes: 0

Anorflame
Anorflame

Reputation: 394

http://en.wikipedia.org/wiki/Dijkstra's_algorithm - you remember that it processes ALL of a vertex's neighbours before moving on to another vertex, right? Before moving on to D, it processes C and B (calculates their distances). And judging from your graph, there is no route between D and F..

Upvotes: 0

mnmnc
mnmnc

Reputation: 374

From C you still cannot go back to A and you cannot return to F so this path is false. You need to remove the C from the graph at next iteration if it gives you dead-end, or ignore last step and move from F to I as you would expect.

Upvotes: 0

Related Questions