Dijkstra's Shortest Path algorithm

[Roy Katz]

On Sat, 9 Dec 2000, Jürgen Hermann wrote:

> Maybe you should try to implement it in Python and NOT take 2-3 days. ;))


I've looked around on google and found a visual graph solver applet coded
(presumably) in Python; I have to check it out.  I've also checked out
www.python.org/docs/essay/graphs.html;  it lists a beginnings of a Graph 
class (sans Dijkstra's algorithm).  

consider something simple:



 Class Graph:


   adjMatrix = None  # array.array? all we need are int's. (NxN matrix)
   cost      = []    # cost from nodeFrom to all other nodes
   pred      = []    # predecessors of every node
   visited   = []    # boolean array symbolizing who has been processed

   # add a vertex
   def addVertex( node ): pass

   # add a (weighted) edge
   def addEdge( nodeFrom, nodeTo, cost ): pass

   # returns array of nodes representing a path;
   # empty path denotes nodeFrom == nodeTo; 
   # None represents no connection between 
   # nodeFrom and nodeTo.

   def shortestPath( nodeFrom, nodeTo ): pass

   # computes cost from nodeFrom to every other node and
   # stores it in self.cost; also builds 'self.pred' array.
   # uses a heap (for the more moderately-sized graphs),
   # otherwise a simple array.

   def dijkstraHelper( nodeFrom ): pass



coded as a C++ extension (I say C++ because I used C++ for my
assignment).  Conceptually, the class would involve an adjacency matrix to
store the edge weights, and some small list (or dictionary) to act as a
lookup table.  shortestPath, after calling dijkstraHelper(),  would use
The lookup table to map vertex integers to objects as it builds the path. 

I can imagine many situations in which I'd want to use something like 
this.  Unfortunately, as finals approach, I don't think I have the time to
code this up :).  



Roey


2nd year, Computer Engineering 
University of Maryland, USA