Faster special-case of Dijkstra

from collections import deque

def shortest_path(graph, source, destination):
    """
    Test/Example of usage:

    >>> A, B, C, D = 'ABCD'
    >>> shortest_path({A:{A:0,B:0,C:1,D:2},\
                       B:{A:0,B:0,C:2,D:2},\
                       C:{A:1,B:2,C:0,D:0},\
                       D:{A:2,D:2,C:0,D:0}},\
                       A, D)
    1
    >>> shortest_path({A:{    B:2,       },\
                       B:{A:2,    C:2,   },\
                       C:{    B:2,    D:2},\
                       D:{        C:2,   }},\
                       A, D)
    6
    """
    current_distance = 0
    processed_nodes = set()

    # For i in {0,1,2}: qs[i] is a queue of nodes whose
    # minimum distance from source is current_distance+i.
    qs = deque([deque([source]), deque(), deque()])

    # while there are reachable, unprocessed nodes...
    while any(qs):
        closest = qs[0]
        while closest:
            # for each node that's current_distance away from source...
            node = closest.popleft()
            if node == destination:
                return current_distance
            processed_nodes.add(node)

            # ... add its unprocessed neighbors to the appropriate queue.
            for neighbor, edge in graph[node].items():
                if neighbor not in processed_nodes:
                    qs[edge].append(neighbor)

        # now that the first queue is empty,
        # start examining the next closest nodes.
        current_distance += 1
        # remove the used-up qs[0] and add a
        # new qs[2] to hold the nodes that are
        # current_distance+2 away.
        qs.append(qs.popleft())


import doctest
doctest.testmod()