# Dijkstra.py

May 1st, 2012
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import random
2.
3. random.seed()
4.
5. class Vertex(object):
6.     __slots__ = ('name',)
7.     def __init__(self, name):
8.         self.name = name
9.
10.     def __str__(self):
11.         return self.name
12.
13.     def __repr__(self):
14.         return self.name
15.
16.
17. class Edge(object):
18.     __slots__ = ('u', 'v', 'd')
19.     def __init__(self, u, v, d):
20.         assert isinstance(u, Vertex) # source vertex
21.         assert isinstance(v, Vertex) # destination vertex
22.         assert isinstance(d, float) # distance, or cost
23.         self.u = u
24.         self.v = v
25.         self.d = d
26.     def __str__(self):
27.         return "[%s --%3.2f--> %s]" % (self.u.name, self.d, self.v.name)
28.     def __repr__(self):
29.         return str(self)
30.
31. class Graph(object):
32.     def __init__(self):
33.         V = []
34.
35.         for n in xrange(100):
36.             V.append(Vertex(str(n + 1)))
37.
38.         E = []
39.         for n in xrange(10*len(V)):
40.             u = V[random.randint(0, len(V) - 1)]
41.             while True:
42.                 v = V[random.randint(0, len(V) - 1)]
43.                 if v is not u:
44.                     break
45.             E.append(Edge(u, v, random.uniform(10, 100)))
46.
47.         self.V = V
48.         self.E = E
49.
50.     def distance(self, s, S):
51.         for edge in (e for e in G.E if e.u == s and e.v == S[0]):
52.             d = edge.d
53.             break
54.         else:
55.             raise AssertionError
56.
57.         for u, v in zip(S[:-1], S[1:]):
58.             for edge in (e for e in G.E if e.u == u and e.v == v):
59.                 d += edge.d
60.                 break
61.             else:
62.                 raise AssertionError
63.         return d
64.
65.
66. def dijkstra(G, t, s):
67.     d = {}
68.     previous = {}
69.     for v in G.V:
70.         d[v] = 1e50 # infinity
71.         previous[v] = None
72.     del v
73.     d[s] = 0
74.     S = []
75.     Q = list(G.V)
76.
77.     def Extract_Min(Q):
78.         m = None
79.         md = None
80.         for u in Q:
81.             if m is None:
82.                 m = u
83.                 md = d[u]
84.             else:
85.                 if d[u] < md:
86.                     md = d[u]
87.                     m = u
88.         Q.remove(m)
89.         return m
90.
91.     while Q:
92.         u = Extract_Min(Q)
93.         if u == t:
94.             break
95.         S.append(u)
96.         for edge in (e for e in G.E if e.u == u):
97.             if d[u] + edge.d < d[edge.v]:
98.                 d[edge.v] = d[u] + edge.d
99.                 previous[edge.v] = u
100.
101.     S = []
102.     u = t
103.     while previous[u] is not None:
104.         S.insert(0, u)
105.         u = previous[u]
106.     return S
107.
108. if __name__ == '__main__':
109.     for n in xrange(7):
110.         G = Graph()
111.         s = G.V[random.randint(0, len(G.V) - 1)]
112.         while True:
113.             t = G.V[random.randint(0, len(G.V) - 1)]
114.             if t is not s:
115.                 break
116.         S = dijkstra(G, t, s)
117.         if S:
118.             print "dijkstra %s ---> %s: " % (s, t), S, G.distance(s, S)
119.             for inter in S[:-1]:
120.                 S1 = dijkstra(G, t, inter)
121.                 print "\t => dijkstra %s ---> %s: " % (inter, t), S1, G.distance(inter, S1)
122.                 if S1 != S[ (len(S) - len(S1)) : ]:
123.                     print "************ ALARM! **************"
RAW Paste Data