bangnaga

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