codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#!/usr/bin/env python def make_heap(): return [] def find_min(h): return h[0] def insert(x, h): return merge([x], h) def merge(h1, h2): if h1 == []: return h2 elif h2 == []: return h1 elif h1[0] < h2[0]: return [h1[0], h2 + h1[1:]] else: return [h2[0], h1 + h2[1:]] def merge_pairs(h): if h == []: return h elif len(h) == 1: return h[0] else: return merge(merge(h[0], h[1]), merge_pairs(h[2:])) def delete_min(h): if h == []: raise IndexError elif len(h[1:]) == 0: return [] elif len(h[1:]) == 1: return h[1:] else: return merge_pairs(h[1:]) class Vertex(object): def __init__(self, adj={}, dist=float("inf"), name=None, pred=None): self.adj = adj self.dist = dist self.name = name self.pred = pred return def __cmp__(self, other): return cmp(self.dist, other.dist) def __repr__(self): return self.name def add_edge(D, u, v, weight): if u not in D: D[u] = Vertex(name=u, adj={}) if v not in D: D[v] = Vertex(name=v, adj={}) D[u].adj[v] = weight return def add_edges(D, edges): for edge in edges: add_edge(D, *edge) return def init_single_source(D, s): for v in D: D[v].dist = float("inf") D[v].pred = None D[s].dist = 0 return def relax(D, u, v): d = D[u].dist + D[u].adj[v] if D[v].dist > d: D[v].dist = d D[v].pred = u return def dijkstra(D, s): init_single_source(D, s) Q = make_heap() for v in D.values(): Q = insert(v, Q) while Q: u, Q = find_min(Q), delete_min(Q) for v in u.adj: relax(D, u.name, v) Q = merge_pairs(Q) return def find_shortest_path(D, s, f): dijkstra(D, s) path, v = [f], D[f].pred while v is not None: path.append(v) v = D[v].pred path.reverse() return path if __name__ == "__main__": D = {} add_edges(D, [('a', 'c', 2), ('a', 'd', 6), ('b', 'a', 3), ('b', 'd', 8), ('c', 'd', 7), ('c', 'e', 5), ('d', 'e', 10)]) print find_shortest_path(D, 'a', 'e')
Private
[
?
]
Run code
Submit