def Dijkstra(grafo, origen, destino):
    """
    Implementación del algoritmo de Dijkstra para encontrar el camino más corto entre un nodo origen y un nodo destino en un grafo ponderado.
    
    Parámetros:
    - grafo: Un diccionario que representa el grafo ponderado. Las claves son los nodos del grafo y los valores son diccionarios que contienen los nodos adyacentes como claves y sus respectivos pesos como valores.
    - origen: El nodo de origen desde el cual se inicia la búsqueda del camino más corto.
    - destino: El nodo de destino al cual se desea llegar desde el nodo origen.
    
    Devuelve:
    - distancias: Un diccionario que contiene las distancias mínimas desde el nodo origen hasta cada nodo del grafo. Las claves son tuplas (origen, destino) y los valores son las distancias mínimas.
    - camino: Una lista que representa el camino más corto desde el nodo origen hasta el nodo destino. Si no hay un camino entre el origen y el destino, devuelve una lista vacía.
    
    Nota:
    - Si no hay un camino desde el origen hasta el destino, el camino devuelto será una lista vacía.
    - Los pesos de las aristas deben ser números enteros o flotantes. Si un peso es 'inf', se interpreta como un camino no disponible.
    """

    # Inicialización
    L = {(origen, nodo): float('inf') for nodo in grafo}  # L(origen, v) para todos los nodos es infinito
    L[(origen, origen)] = 0  # L(origen, origen) = 0 para el nodo inicial
    S = set()  # S es el conjunto vacío
    camino_previo = {nodo: None for nodo in grafo}  # Para reconstruir el camino más corto

    while len(S) < len(grafo):
        # u := vértice con L(u) mínima entre los vértices que no están en S
        u = min(((origen, nodo) for nodo in grafo if (origen, nodo) not in S), key=lambda nodo: L[nodo])

        # Añadir u al conjunto S
        S.add(u)

        # Para todos los vértices v que no están en S
        for v, peso in grafo[u[1]].items():
            if (origen, v) not in S:
                # if L(u) + w(u, v) < L(v) then L(v) := L(u) + w(u, v)
                if peso == 'inf':
                    peso = float('inf')
                if L[u] + peso < L[(origen, v)]:
                    L[(origen, v)] = L[u] + peso
                    camino_previo[v] = u[1]  # Guardar el nodo previo para reconstruir el camino

    # Reconstruir el camino más corto desde el origen hasta el destino
    nodo_actual = destino
    camino = []
    while nodo_actual is not None:
        camino.insert(0, nodo_actual)  # Insertar al inicio para obtener el camino en orden 'a' -> 'z'
        nodo_actual = camino_previo[nodo_actual]

    return L, camino

# Representación del grafo de la Figura 4 (pág 559 K. Rosen)
grafo = {
  'a': {'b': 4, 'c': 2, 'd': 'inf', 'e': 'inf', 'z': 'inf'},
  'b': {'a': 4, 'c': 1, 'd': 5, 'e': 'inf', 'z': 'inf'},
  'c': {'a': 2, 'b': 1, 'd': 8, 'e': 10, 'z': 'inf'},
  'd': {'a': 'inf', 'b': 5, 'c': 8, 'e': 2, 'z': 6},
  'e': {'a': 'inf', 'b': 'inf', 'c': 10, 'd': 2, 'z': 3},
  'z': {'a': 'inf', 'b': 'inf', 'c': 'inf', 'd': 6, 'e': 3}
}

nodo_origen = 'a'
nodo_destino = 'z'
distancias, camino = Dijkstra(grafo, nodo_origen, nodo_destino)
distancia_total = distancias[(nodo_origen, nodo_destino)]
print("Distancias mínimas:", {f"{nodo_origen}-{nodo}": distancia for (origen, nodo), distancia in distancias.items() if origen == nodo_origen})
print(f"El camino más corto desde el nodo {nodo_origen} hasta el nodo {nodo_destino} es: {', '.join(camino)}, con una longitud de {distancia_total}")