Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random
- random.seed()
- class Vertex(object):
- __slots__ = ('name',)
- def __init__(self, name):
- self.name = name
- def __str__(self):
- return self.name
- def __repr__(self):
- return self.name
- class Edge(object):
- __slots__ = ('u', 'v', 'd')
- def __init__(self, u, v, d):
- assert isinstance(u, Vertex) # source vertex
- assert isinstance(v, Vertex) # destination vertex
- assert isinstance(d, float) # distance, or cost
- self.u = u
- self.v = v
- self.d = d
- def __str__(self):
- return "[%s --%3.2f--> %s]" % (self.u.name, self.d, self.v.name)
- def __repr__(self):
- return str(self)
- class Graph(object):
- def __init__(self):
- V = []
- for n in xrange(100):
- V.append(Vertex(str(n + 1)))
- E = []
- for n in xrange(10*len(V)):
- u = V[random.randint(0, len(V) - 1)]
- while True:
- v = V[random.randint(0, len(V) - 1)]
- if v is not u:
- break
- E.append(Edge(u, v, random.uniform(10, 100)))
- self.V = V
- self.E = E
- def distance(self, s, S):
- for edge in (e for e in G.E if e.u == s and e.v == S[0]):
- d = edge.d
- break
- else:
- raise AssertionError
- for u, v in zip(S[:-1], S[1:]):
- for edge in (e for e in G.E if e.u == u and e.v == v):
- d += edge.d
- break
- else:
- raise AssertionError
- return d
- def dijkstra(G, t, s):
- d = {}
- previous = {}
- for v in G.V:
- d[v] = 1e50 # infinity
- previous[v] = None
- del v
- d[s] = 0
- S = []
- Q = list(G.V)
- def Extract_Min(Q):
- m = None
- md = None
- for u in Q:
- if m is None:
- m = u
- md = d[u]
- else:
- if d[u] < md:
- md = d[u]
- m = u
- Q.remove(m)
- return m
- while Q:
- u = Extract_Min(Q)
- if u == t:
- break
- S.append(u)
- for edge in (e for e in G.E if e.u == u):
- if d[u] + edge.d < d[edge.v]:
- d[edge.v] = d[u] + edge.d
- previous[edge.v] = u
- S = []
- u = t
- while previous[u] is not None:
- S.insert(0, u)
- u = previous[u]
- return S
- if __name__ == '__main__':
- for n in xrange(7):
- G = Graph()
- s = G.V[random.randint(0, len(G.V) - 1)]
- while True:
- t = G.V[random.randint(0, len(G.V) - 1)]
- if t is not s:
- break
- S = dijkstra(G, t, s)
- if S:
- print "dijkstra %s ---> %s: " % (s, t), S, G.distance(s, S)
- for inter in S[:-1]:
- S1 = dijkstra(G, t, inter)
- print "\t => dijkstra %s ---> %s: " % (inter, t), S1, G.distance(inter, S1)
- if S1 != S[ (len(S) - len(S1)) : ]:
- print "************ ALARM! **************"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement