class Graph: def __init__ (self): self.V = [] self.w = {} class Vertex: def __init__ (self, x): self

class Graph: def __init__ (self): self.V = [] self.w = {} class Vertex: def __init__ (self, x): self.key = x self.color = ' white ' self.d = 10000 self.pi = None self.adj = [] class Solution(): def InitializeSingleSource(self, G, s): for v in G.V: v.d = 10000 v.pi = None s.d = 0 def Relax(self, u, v, w): if v.d > u.d + w[(u, v)]: v.d = u.d + w[(u, v)] v.pi = u def Dijkstra(self, G, w, s): self.InitializeSingleSource(G, s) S = set() Q = G.V[:] while Q != []: u = self.ExtractMin(Q, S) S.add(u) for v in u.adj: self.Relax(u, v, w) def ExtractMin(self, Q, S): Q.sort(key = lambda v: v.d) return Q.pop(0) if __name__ == ' __main__ ' : s = Vertex( comm ' s ' ) t = Vertex( ' t ' ) y = Vertex( ' y ' ) x = Vertex( ' x ' ) z = Vertex( ' z ' ) s.adj = [t, y] y.adj = [t, z, x] t.adj = [x, y] x.adj = [z] z.adj = [x, s] G = Graph() G.V = [s, t, y, x, z] G.w = { (s,t): 10 , (s,y): 5 , (t,y): 2 , (y,t): 3 , (t,x): 1 , (y,z): 2 , (x,z): 4 , (z,x): 6 , (y,x): 9 , (z,s): 7 } m = Solution() m.Dijkstra(G, G.w, s) for v in G.V: if v != s: print v.key, v.d, v.pi.key else : print v.key, v.d, v.pi