#
# improved version of Dijkstra's algorithm...
#

def dijkstra(graph, start):
    """
    Dijkstra's algorithm Python implementation.

    Arguments:
        graph: Dictionnary of dictionnary (keys are vertices).
        start: Start vertex.
        end: End vertex.

    Output:
        List of vertices from the beggining to the end.

    Example:

    >>> graph = {
    ...     'A': {'B': 10, 'D': 4, 'F': 10},
    ...     'B': {'E': 5, 'J': 10, 'I': 17},
    ...     'C': {'A': 4, 'D': 10, 'E': 16},
    ...     'D': {'F': 12, 'G': 21},
    ...     'E': {'G': 4},
    ...     'F': {'H': 3},
    ...     'G': {'J': 3},
    ...     'H': {'G': 3, 'J': 5},
    ...     'I': {},
    ...     'J': {'I': 8},
    ... }    
    >>> Dists, Preds = dijkstra(graph, 'C')
    >>> printDistsPreds( 'C', Dists, Preds )

    """

    D = {} # Final distances dict
    P = {} # Predecessor dict

    # Fill the dicts with default values
    for node in graph.keys():
        D[node] = float('inf') # Vertices are unreachable
        P[node] = "" # Vertices have no predecessors

    D[start] = 0 # The start vertex needs no move

    unseen_nodes = graph.keys() # All nodes are unseen

    while len(unseen_nodes) > 0:
        # Select the unexpanded node with the lowest value in D
        shortest = None
        node = ''
        for temp_node in unseen_nodes:
            if shortest == None:
                shortest = D[temp_node]
                node = temp_node
            elif D[temp_node] < shortest:
                shortest = D[temp_node]
                node = temp_node

        # Remove the selected node from unseen_nodes
        unseen_nodes.remove(node)

        # For each child (ie: connected vertex) of the current node
        for child_node, child_value in graph[node].items():
            if D[child_node] > D[node] + child_value:
                D[child_node] = D[node] + child_value
                # To go to child_node, you have to go through node
                P[child_node] = node


    return D, P

def printDistsPreds( start, D, P ):
    """ prints distances and predecessors """
    print "Minimum distances from", start, ":"
    for k in D:
        print "  to", k, "=", D[k]

    print
    print
    print "Paths of minimum distance from", start, ":"
    for k in P:
        path = getPath( start, k, P )
        print "  to", k, "=", path

    print
    print


def getPath( start, end, P ):
    # We begin from the end
    node = end
    # no path yet!
    path = []
    # While we are not arrived at the beginning
    while not (node == start):
        if path.count(node) == 0: # no cycles!
            path.insert(0, node) # Insert the predecessor of the current node
            node = P[node] # The current node becomes its predecessor
        else:
            break

    path.insert(0, start) # Finally, insert the start vertex
    return path


if __name__ == "__main__":
  graph = { 'A': {'B': 10, 'D': 4, 'F': 10},
            'B': {'E': 5,  'J': 10, 'I': 17},
            'C': {'A': 4,  'D': 10, 'E': 16},
            'D': {'F': 12, 'G': 21},
            'E': {'G': 4},
            'F': {'H': 3},
            'G': {'J': 3},
            'H': {'G': 3,  'J': 5},
            'I': {},
            'J': {'I': 8},
        }
 
  Distances, Predecessors = dijkstra( graph, 'C' )
  D = Distances
  P = Predecessors
  printDistsPreds( 'C', D, P )