1+ import sys
2+
3+ class Vertex :
4+ def __init__ (self , node ):
5+ self .id = node
6+ self .adjacent = {}
7+ # Set distance to infinity for all nodes
8+ self .distance = sys .maxint
9+ # Mark all nodes unvisited
10+ self .visited = False
11+ # Predecessor
12+ self .previous = None
13+
14+ def add_neighbor (self , neighbor , weight = 0 ):
15+ self .adjacent [neighbor ] = weight
16+
17+ def get_connections (self ):
18+ return self .adjacent .keys ()
19+
20+ def get_id (self ):
21+ return self .id
22+
23+ def get_weight (self , neighbor ):
24+ return self .adjacent [neighbor ]
25+
26+ def set_distance (self , dist ):
27+ self .distance = dist
28+
29+ def get_distance (self ):
30+ return self .distance
31+
32+ def set_previous (self , prev ):
33+ self .previous = prev
34+
35+ def set_visited (self ):
36+ self .visited = True
37+
38+ def __str__ (self ):
39+ return str (self .id ) + ' adjacent: ' + str ([x .id for x in self .adjacent ])
40+
41+ class Graph :
42+ def __init__ (self ):
43+ self .vert_dict = {}
44+ self .num_vertices = 0
45+
46+ def __iter__ (self ):
47+ return iter (self .vert_dict .values ())
48+
49+ def add_vertex (self , node ):
50+ self .num_vertices = self .num_vertices + 1
51+ new_vertex = Vertex (node )
52+ self .vert_dict [node ] = new_vertex
53+ return new_vertex
54+
55+ def get_vertex (self , n ):
56+ if n in self .vert_dict :
57+ return self .vert_dict [n ]
58+ else :
59+ return None
60+
61+ def add_edge (self , frm , to , cost = 0 ):
62+ if frm not in self .vert_dict :
63+ self .add_vertex (frm )
64+ if to not in self .vert_dict :
65+ self .add_vertex (to )
66+
67+ self .vert_dict [frm ].add_neighbor (self .vert_dict [to ], cost )
68+ self .vert_dict [to ].add_neighbor (self .vert_dict [frm ], cost )
69+
70+ def get_vertices (self ):
71+ return self .vert_dict .keys ()
72+
73+ def set_previous (self , current ):
74+ self .previous = current
75+
76+ def get_previous (self , current ):
77+ return self .previous
78+
79+ def shortest (v , path ):
80+ ''' make shortest path from v.previous'''
81+ if v .previous :
82+ path .append (v .previous .get_id ())
83+ shortest (v .previous , path )
84+ return
85+
86+ import heapq
87+
88+ def dijkstra (aGraph , start , target ):
89+ print '''Dijkstra's shortest path'''
90+ # Set the distance for the start node to zero
91+ start .set_distance (0 )
92+
93+ # Put tuple pair into the priority queue
94+ unvisited_queue = [(v .get_distance (),v ) for v in aGraph ]
95+ heapq .heapify (unvisited_queue )
96+
97+ while len (unvisited_queue ):
98+ # Pops a vertex with the smallest distance
99+ uv = heapq .heappop (unvisited_queue )
100+ current = uv [1 ]
101+ current .set_visited ()
102+
103+ #for next in v.adjacent:
104+ for next in current .adjacent :
105+ # if visited, skip
106+ if next .visited :
107+ continue
108+ new_dist = current .get_distance () + current .get_weight (next )
109+
110+ if new_dist < next .get_distance ():
111+ next .set_distance (new_dist )
112+ next .set_previous (current )
113+ print 'updated : current = %s next = %s new_dist = %s' \
114+ % (current .get_id (), next .get_id (), next .get_distance ())
115+ else :
116+ print 'not updated : current = %s next = %s new_dist = %s' \
117+ % (current .get_id (), next .get_id (), next .get_distance ())
118+
119+ # Rebuild heap
120+ # 1. Pop every item
121+ while len (unvisited_queue ):
122+ heapq .heappop (unvisited_queue )
123+ # 2. Put all vertices not visited into the queue
124+ unvisited_queue = [(v .get_distance (),v ) for v in aGraph if not v .visited ]
125+ heapq .heapify (unvisited_queue )
126+
127+ if __name__ == '__main__' :
128+
129+ g = Graph ()
130+
131+ g .add_vertex ('a' )
132+ g .add_vertex ('b' )
133+ g .add_vertex ('c' )
134+ g .add_vertex ('d' )
135+ g .add_vertex ('e' )
136+ g .add_vertex ('f' )
137+
138+ g .add_edge ('a' , 'b' , 7 )
139+ g .add_edge ('a' , 'c' , 9 )
140+ g .add_edge ('a' , 'f' , 14 )
141+ g .add_edge ('b' , 'c' , 10 )
142+ g .add_edge ('b' , 'd' , 15 )
143+ g .add_edge ('c' , 'd' , 11 )
144+ g .add_edge ('c' , 'f' , 2 )
145+ g .add_edge ('d' , 'e' , 6 )
146+ g .add_edge ('e' , 'f' , 9 )
147+
148+ print 'Graph data:'
149+ for v in g :
150+ for w in v .get_connections ():
151+ vid = v .get_id ()
152+ wid = w .get_id ()
153+ print '( %s , %s, %3d)' % ( vid , wid , v .get_weight (w ))
154+
155+ dijkstra (g , g .get_vertex ('a' ), g .get_vertex ('e' ))
156+
157+ target = g .get_vertex ('e' )
158+ path = [target .get_id ()]
159+ shortest (target , path )
160+ print 'The shortest path : %s' % (path [::- 1 ])
0 commit comments