2

Say I have the following graph:

           e (destination)
           |
           | (1)
           |
           d
           |
           | (100)
           |
  (start)  a - - - b - - - c
             (1)      (1)

Would Dijkstra's algorithm run into a dead end? I think if I start from a, it will go a->b->c and went into dead end, therefore cannot reach e. Is that so?

1
  • You have two cs in there - that does not make sense.
    – us2012
    Feb 12, 2013 at 4:10

1 Answer 1

3

Obviously not. From the wikipedia description of Dijkstra's algorithm:

.3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances.

That means that if you start at a, b and d are both examined (i.e. their tentative distances are calculated) because they are unvisited neighbours. Because b has the smaller tentative distance, you visit that one next.

For your update with the extra node e: You arrive at c as described above. But you're not stuck - there is still an unvisited node with a precalculated tentative distance, namely d - so you visit that one next.

3
  • why? from a, you'll decide to go b, and then c. At c, all neighbors are visited.
    – JASON
    Feb 12, 2013 at 4:18
  • 1
    No. As I said, starting from a, you immediately examine b and d. Only after that do you decide to 'go to b'. I don't know what else to say but "read the algorithm's description again".
    – us2012
    Feb 12, 2013 at 4:21
  • I think I do understand the description. Do you? if the sequence is not a->b->c, what it is?
    – JASON
    Feb 12, 2013 at 4:23

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