# Dijkstra's Shortest Path algorithm

Roy Katz katz at Glue.umd.edu
Sun Dec 10 01:12:01 CET 2000

```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

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

```