[ create a new paste ] login | about

Link: http://codepad.org/D1UKwnZS    [ raw code | output | fork ]

gre - Python, pasted on Dec 31:
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')


Output:
1
['a', 'c', 'e']


Create a new paste based on this one


Comments: