codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
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 class DiGraph(dict): def addEdge(self, u, v, weight): if u not in self: self[u] = Vertex(name=u, adj={}) if v not in self: self[v] = Vertex(name=v, adj={}) self[u].adj[v] = weight return def addEdges(self, edges): for e in edges: self.addEdge(e[0], e[1], e[2]) return def _initSingleSource(self, s): for v in self: self[v].dist = float("inf") self[v].pred = None self[s].dist = 0 return def _relax(self, u, v): d = self[u].dist + self[u].adj[v] if self[v].dist > d: self[v].dist = d self[v].pred = u return def dijkstra(self, s): self._initSingleSource(s) Q = make_heap() for v in self.values(): Q = merge([v], Q) while Q: u = find_min(Q) Q = delete_min(Q) for v in u.adj: self._relax(u.name, v) Q = merge_pairs(Q) return def findShortestPath(self, s, f): self.dijkstra(s) path, v = [f], self[f].pred while v is not None: path.append(v) v = self[v].pred path.reverse() return path if __name__ == "__main__": G = DiGraph() G.addEdges([('a', 'c', 2), ('a', 'd', 6), ('b', 'a', 3), ('b', 'd', 8), ('c', 'd', 7), ('c', 'e', 5), ('d', 'e', 10)]) print G.findShortestPath('a', 'e')
Private
[
?
]
Run code
Submit