[ create a new paste ] login | about

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

gre - Python, pasted on Jan 2:
#!/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')


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


Create a new paste based on this one


Comments: