Doing this with the example on wikipedia on the right:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
start with distance values to each of the nodes as
d2: inf, inf
d3: inf, inf
d4: inf, inf
d5: inf, inf
d6: inf, inf
We have 6 nodes with following edge weights from 1:
(12) - 7, (13) - 9, (16) - 14
So we set
d2 := 7, inf
d3 := 9, inf
d6 := 14, inf
Next round:
(23) = 10, (24) = 15. Here is where it gets a little tricky. Do the incoming edges to 2 first, to find the second edge.
d2:= 7, 19 (19 is 9 + edge of 10)
then set the other vertices:
d3:= 9, 17
d4:= 22, 34
Total:
*d2: 7, 19
d3: 9, 17
d4: 22, 34
d5: inf, inf
d6: 14, inf
Next round:36 = 2, 34 = 11
d3:= 9, 16
There might be some more backtracking, so we double check, 16 + (32) = 16 + 10 = 26 > 19. No more back tracking needed
d6:= 11, 14 (quick back check of edges from 6 reveals no updates needed)
d4, comparing, 20, 27 with 22, 34, we get
d4:= 20, 22
Total:
*d2: 7, 19
*d3: 9, 16
d4: 20, 22
d5: inf, inf
d6: 11, 14
Next is 6: (65) = 9
*d2: 7, 19
*d3: 9, 16
d4: 20, 22
d5: 20, 23
*d6: 11, 14
Finally, we have 4: (45) = 6
d4 + 45 = 26, 28. comparing to 20, 23 nothing changes.
End result:
*d2: 7, 19
*d3: 9, 16
*d4: 20, 22
*d5: 20, 23
*d6: 11, 14
Finding the path back:
You could also store where the last 2 edges came from, to do this quickly. However, it requires more space.
the 2nd furthest path to d5 is 23.
23 - (54) = 17, doesn't match
23 - (56) = 14. Match
14 - (61) = 0 Match (since node 1 implicitly contains values (0, inf).
The second furthest path to node 5 from 1 is 1 - 6 - 5