# file: kortstepad1.py
# Dijkstra's algorithm
# graph representation: dictionary, see Python Patterns:
# http://www.python.org/doc/essays/graphs.html
# note: this actually represents a directed graph, OK for this algorithm
# 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}
}
graph = G1
# starting point is startnode
# bookkeeping: for every node, we keep the distance to startnode; initially, this is
# infinite, except for startnode, where it is 0
# ** lines marked in this way do not belong to the algorithm proper, just for illustration
maxdist = 100000 # "infinite" distance
startnode = 'A' # set startnode
setA = set([startnode]) # represents Dijkstra's set "A": shortest distance determined
dist = {startnode:0} # startnode with distance 0
for v in graph: # other nodes have infinite initial distance
if v != startnode:
dist.update({v:maxdist})
setX = set([]) # dijkstra's set "X": nodes directly connected to nodes in "A"
cnt = 0 # ** to estimate number of steps in algorithm execution
# update the distance (from A) for the nodes reachable via node r
def relax (r):
global cnt # **
for v in graph[r]: # v: targets of outgoing edges from r
if not v in setA:
cnt = cnt + 1 # **
setX.add (v)
if dist[r]+graph[r][v] < dist[v]:
dist[v] = dist[r]+graph[r][v]
relax(startnode)
print "X=", setX # **
while len(setX)>0:
min=maxdist
for v in setX:
cnt = cnt + 1 # **
if dist[v] < min:
min = dist[v]
vmin = v
setX.remove(vmin)
setA.add(vmin)
relax(vmin)
print "vmin=", vmin, "dist=", dist[vmin], "X=", setX # **
print "dist", dist # **
print "cnt=", cnt # **