Dijkstra's Algorithm With Back Tracking?

In a related thread, it was suggested that I impliment Dijkstra's algorithm for finding the shortest path on a graph. Looking at this .gif of the algorithm from wikipedia: What i

Solution 1:

Dijkstra algorithm always finds the shortest path (in graphs without negative edges) and never backtracks. It is easy to reason about it.

Always choosing the minimum

Think about a node and its edges (it's just part of a larger graph):

    6   _ 3
    |  /
  14| /9
    |/
    1-------2
        7  

Dijkstra's algorithm will begin choosing the edge 1-2 (7). I does so because it is the minimum it has seen so far. It then sets the value of the shortest path to 2 as 7. It will never change this value again, because any other path from 1 to 2 must be larger (as it must start with one of the edges 1-3 (9) or 1-6 (14)).

Consider the known nodes as a single node

One way to reason about what comes next is to pretend the algorithm merges "known" nodes into a single one. In the example, as soon as the shortest path to 2 is chosen, it merges 1 and 2 as a single logical node. All edges going out of 2 are increased by 7 (the shortest path to 2). The next step is to choose the smallest edge outgoing from the "supernode". The reasoning then is the same as the first step:

    6   _ 3
    |  /
  14| /9
    |/
   1,2-------4
        22  

In this state, the next chosen edge is 1,2-3 (9). The shortest path to 3 is set as 9 and all of its edges are now considered to choose the next minimum (please note how the edges to 6 and 4 have been updated):

    6
    |
  11|
    |
   1,2,3----4
         20  

Solution 2:

It would not skip node 3. It would do this:

Start from node 1, update distances to neighbours:

d[2] = 7
d[3] = 9
d[6] = 14

Pick the next unvisited node with distance from source minimum, in this case node 2 and update the distances to its neighbors:

d[3] = min(d[3], d[2] + c(2, 3))
     = min(9, 7 + 10)
     = 9

d[4] = min(d[4], d[2] + c(2,4))
     = min(inf, 7 + 15)
     = 22

Then it will pick 3: update the distances to its neighbours:

d[6] = min(d[6], d[3] + c(3, 6))
     = min(14, 9 + 1)
     = 10

Then pick the next unvisited node with distance d minimum and do the same. Stop when you pick your destination node.

There is no need to do what you suggest, the algorithm will work just fine as long as your edge weights are positive.