# file: kortstepad0.py
# First step towards Dijkstra's algorithm
# graph representation: dictionary, see Python Patterns:
# http://www.python.org/doc/essays/graphs.html
# note: this actually represents a directed graph;
# for our use (undirected graph), we duplicate all connections
# G[n] is the set of edges from n
# G[n][m] is the length of the edge from n to m
G0 = { 'A': {'B':3, 'C':11, 'D':9},
'B': {'A':3, 'C':4, 'D':5},
'C': {'A':11, 'B':4, 'D':3},
'D': {'A':9, 'B':5, 'C':3},
}
# The next example is obtained from
# http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/DijkstraApp.shtml?demo2
G1 = { 'A': {'B':1, 'E':3},
'B': {'A':1, 'C':2, 'E':1, 'F':6, 'G':2},
'C': {'B':2, 'D':3, 'G':5, 'H':1},
'D': {'C':3, 'H':2},
'E': {'A':3, 'B':1, 'F':3, 'I':2, 'J':1},
'F': {'B':6, 'E':3, 'G':1, 'J':1},
'G': {'B':2, 'C':5, 'F':1, 'H':1, 'J':1, 'K':3, 'L':2},
'H': {'C':1, 'D':2, 'G':1, 'L':3},
'I': {'E':2, 'J':2, 'M':4},
'J': {'E':1, 'F':1, 'G':1, 'I':2, 'K':2, 'N':1, 'O':5},
'K': {'J':2, 'G':3, 'L':2, 'O':2, 'P':2},
'L': {'G':2, 'H':3, 'K':2, 'P':1},
'M': {'I':4, 'N':2},
'N': {'I':5, 'J':1, 'M':2, 'O':1},
'O': {'J':5, 'K':2, 'N':1, 'P':2},
'P': {'K':3, 'L':1, 'O':2}
}
# start node point is startnode
# bookkeeping: for every node, we keep the distance to startnode; initially, this is
# infinite, except for stratnode, where it is 0
# for every node with known distance to startnode, we keep the predecessor in the path
# from startnode (this is not needed for Dijkstra's algorithm, but is useful to construct
# the actual paths)
graph = G1
startnode = 'A'
maxdist = 100000
dist = {startnode:0} # shortest distance (if determined) to startnode
for v in graph: # initially, 0 for startnode, maxdist for other nodes
if v != startnode:
dist.update({v:maxdist})
rest = graph.keys()
rest.remove(startnode)
cnt = 0 # ** to estimate number of steps in computation
while len(rest)>0:
mindist=maxdist
for v in rest:
for n in graph[v]: # edges from v, to n
cnt = cnt+1
vdist = dist[n]+graph[v][n]
if vdist < mindist:
mindist = vdist
vmin = v
rest.remove(vmin)
dist[vmin] = mindist
print "vmin=", vmin, "dist=", mindist
print "cnt=", cnt
print "dist", dist