simple djikstra

djikstra.py

import heapq

def djikstra(graph, s, z):
    dist = {s:0}
    pred = {s:None}
    visited = {}
    q = []
    heapq.heappush(q, s)

    while q:
        u = heapq.heappop(q)
        visited[u] = True

        if u == z:
            break

        for n, c in graph[u]:
            if not visited.get(n, False):
                if dist.get(n, float('inf')) > dist[u] + c:
                    dist[n] = dist[u] + c
                    pred[n] = u
                heapq.heappush(q, n)

    return dist[z], pred


G = { 'a' : [('b', 6), ('c', 2)],
        'b' : [('a', 6), ('c', 3), ('d', 1), ('e', 4)],
        'c' : [('a', 2), ('b', 3), ('d', 1)],
        'd' : [('c', 1), ('b', 1), ('e', 6)],
        'e' : [('b', 4), ('d', 6)]
        }
djikstra(G, 'a', 'e')