Modify Dijkstra's algorithm to get the shortest path between two nodes

Question

So, I saw similar questions to this, but not exactly what I'm looking for. I need to modify the Dijkstra Algorithm to return the shortest path between vertex S (source) and vertex X (destination). I think I understood what to do, but I need help. Here is the updated pseudo code.

1 function Dijkstra(Graph, source, destination): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity ; // Unknown distance function from 4 // source to v 5 previous[v] := undefined ; // Previous node in optimal path 6 end for // from source 7 8 dist[source] := 0 ; // Distance from source to source 9 Q := the set of all nodes in Graph ; // All nodes in the graph are 10 // unoptimized - thus are in Q 11 while Q is not empty: // The main loop 12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case 13 remove u from Q ; 14 if dist[u] = infinity: 15 break ; // all remaining vertices are 16 end if // inaccessible from source 17 18 for each neighbor v of u: // where v has not yet been 19 // removed from Q. 20 alt := dist[u] + dist_between(u, v) ; 21 if alt < dist[v]: // Relax (u,v,a) 22 dist[v] := alt ; 23 previous[v] := u ; 24 decrease-key v in Q; // Reorder v in the Queue 25 end if 26 end for 27 end while 28 return dist[destination]; 

The code was taken from Wikipedia and modified: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Does this look right?

Answer 1

Dijkstra's algorithm does not need to be modified; it is the shortest path algorithm of all pairs. It sounds like you're trying to find the shortest path between two specific nodes - Dijkstra handles this penalty.

If you want something that is specifically designed for an unweighted, undirected chart that you think you are doing, I would suggest making BFS.

Answer 2

After finding the shortest path, starting with a single SOURCE, we need to start with DESTINATION to undo its predecessor in order to print the path.

 Print-Path(G,s,v) { if(v==s) print s; else if (pi[v]==NULL) print "no path from "+s+" to "+v; else{ Print-Path(G,s,pi[v]) print v; } } 

the codes above are kindly provided for introduction to the algorithm, MIT press

Answer 3

The best way to get closer to this is to think in terms of paths from each reachable node to the source, usually denoted by v. When you update each given distance of a node, track its direct successor on this path to v. This node is the given parent of the node in the shortest distance tree to v. When you built this parent map, find the shortest path from v to w, building the path in reverse order: w, parent [w], parent [parent [w]], ...