Dijkstra

def dijkstra(grafo,fuente,destino,visitadas=[],distancias={},predecesores={}):
    '''
        Algoritmo de Dijkstra - calcular trayectoria entre dos ciudades
    '''
    if fuente not in grafo:
        raise TypeError('No se encontro la ciudad raiz dentro del grafo')
    if destino not in grafo:
        raise TypeError('no se pudo encontrar la trayectoria dentro del grafo')
    if fuente == destino:
        # We build the shortest camino and display it
        camino=[]
        pred=destino
        while pred != None:
            camino.append(pred)
            pred=predecesores.get(pred,None)
        print str(camino)
    else :
        if not visitadas:
            distancias[fuente]=0
        for vecino in grafo[fuente] :
            if vecino not in visitadas:
                distancia_nueva = distancias[fuente] + grafo[fuente][vecino]
                if distancia_nueva < distancias.get(vecino,float('inf')):
                    distancias[vecino] = distancia_nueva
                    predecesores[vecino] = fuente
        visitadas.append(fuente)
        sinvisitar={}
        for k in grafo:
            if k not in visitadas:
                sinvisitar[k] = distancias.get(k,float('inf'))
        x=min(sinvisitar, key=sinvisitar.get)
        dijkstra(grafo,x,destino,visitadas,distancias,predecesores)



if __name__ == "__main__":
    grafo = {
            'c1': {'c2': 1},
            'c2': {'c3': 1},
            'c3': {},
            'c4': {'c5': 1, 'c6': 1},
            'c5': {'c6': 1},
            'c6': {}
    }
    dijkstra(grafo,'c1','c3')