Dijkstra algorithm

shortest_path.py

import sys


def shortest_path(g, start, end):
    """
    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:

    >>> g = {
    ...     '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},
    ... }    
    >>> shortest_path(g, 'C', 'I')
    ['C', 'A', 'B', 'I']

    """
    
    intree, distance, parent = {}, {}, {}
    
    for v in g:
        intree[v] = False
        distance[v] = sys.maxint
        parent[v] = ''
    
    distance[start] = 0
    v = start
    
    while v != end and intree[v] is False:
        intree[v] = True
        p = g[v]
        
        for q, weight in p.iteritems():
            if distance[q] > distance[v]+weight:
                distance[q] = distance[v]+weight
                parent[q] = v
                
        v = min((x for x in g if intree[x] is False), key=lambda x:distance[x])
        
        
    if parent[end]:
        path = [end]
        v = end
        while v != start:
            path.append(parent[v])
            v = parent[v]
        
        return path[::-1]
    else:
        return None