CODEWITHSUNDEEP
data-structuresgraphgraph-theorydijkstra
csnate
csnate

Reputation: 1641

Modify Dijkstra's Algorithm to get the Shortest Path Between Two Nodes

So I've seen similar questions to this but not quite exactly what I'm looking for. I need to modify Dijkstra's Algorithm to return the shortest path between a vertex S (source) and a vertex X (destination). I think I've figured out what to do, but I'd like some help. Here is the pseudocode I have modified.

 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 correct?

Upvotes: 7

Views: 22787

Answers (3)

Tom Payne
Tom Payne

Reputation: 31

The best way to approach this is to think in terms of paths from each reachable node back to the source, commonly denoted by v. As you update each given node's distance, keep track of its direct successor on that path to v. That node is the given node's parent in the shortest-distance-to-v tree. When you've built that parent map, to find the shortest path from v to w build the path in reverse order: w, parent[w], parent[parent[w]], ...

Upvotes: 3

Daniel
Daniel

Reputation: 971

After finding the shortest-path starting from the single SOURCE, we need begin with DESTINATION to backtrack 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;
    }
}

codes above courtesy to Introduction to Algorithm, MIT press

Upvotes: 4

adelbertc
adelbertc

Reputation: 7320

Dijkstra's algorithm does not need to be modified, it is an all-pairs shortest path algorithm. It seems like you are trying to find the shortest path between two specific nodes - Dijkstra handles this fine.

If you want something that's designed specifically for an unweighted, undirected graph, which is what it seems like you're doing, I would suggest doing a BFS.

Upvotes: 4

Related Questions