dijsktra_mulit_query.py

from operator import itemgetter

def dijkstra_multi_query(edges, edge_weights, s, terminals):

    # terminals is a set of vertices t that we want to find the distance to
    # given a start vertex s

    count = len(terminals)

    optimal = {} # vertices that we know the min path to { vertex : weight }

    matches = {}

    tentative = {s : 0}

    while tentative:

        if count == 0:
            return matches

        # find the min path weight node and its weight
        (v, w) = min(tentative.items(), key=itemgetter(1))

        del tentative[v] # remove vertex as it has now been visited
        optimal[v] = w   # we know that w is the min weight from s to v

        if v in terminals:
            terminals.remove(v)
            matches[v] = w

        for u in edges[v]:
            if u not in optimal:
                tentative[u] = min(tentative.get(u,float('inf')), optimal[v] + edge_weights[(v,u)])

    for t in terminals:
        matches[t] = 'Impossible'
    return matches




edge_weights = {('a','b'):10, ('a','c'):1, ('b','c'):3, ('b','d'):2, ('c','d'):15, ('d','e'):7,
                ('b','a'):10, ('c','a'):1, ('c','b'):3, ('d','b'):2, ('d','c'):15, ('e','d'):7}

edges = {'a':{'b','c'},
         'b':{'a','c','d'},
         'c':{'a','b','d'},
         'd':{'b','c','e'},
         'e':{'d'}
}

def test():
    print dijkstra_multi_query(edges, edge_weights, 'a', set(['b','c','e','d','x']))