Ejercicio de TDijkastra

import heapq

# Definición del grafo como diccionario de adyacencias
grafo = {
    'A': {'B': 30, 'C': 90},
    'B': {'C': 72, 'D': 30, 'E': 48},
    'C': {'D': 120, 'F': 150, 'G': 180},
    'D': {'E': 100, 'G': 60},
    'E': {'F': 150},
    'F': {'G': 72},
    'G': {}
}

def dijkstra(grafo, inicio, fin):
    # Inicializamos la cola de prioridad con el nodo inicial y distancia 0
    cola, distancias, camino = [(0, inicio)], {inicio: 0}, {}
    
    # Procesamos los nodos en la cola de prioridad
    while cola:
        distancia, nodo = heapq.heappop(cola)
        if nodo == fin:  # Si alcanzamos el nodo destino, terminamos
            break
        # Recorremos los vecinos del nodo actual
        for vecino, peso in grafo[nodo].items():
            nueva_dist = distancia + peso  # Calculamos la nueva distancia
            # Si encontramos una ruta más corta hacia el vecino
            if nueva_dist < distancias.get(vecino, float('inf')):
                distancias[vecino], camino[vecino] = nueva_dist, nodo  # Actualizamos distancia y predecesor
                heapq.heappush(cola, (nueva_dist, vecino))  # Añadimos el vecino a la cola

    # Reconstruimos la ruta óptima desde el nodo destino hacia el inicio
    ruta, paso = [], fin
    while paso:
        ruta.insert(0, paso)  # Insertamos el nodo al inicio de la ruta
        paso = camino.get(paso)  # Retrocedemos usando el diccionario de predecesores
    
    # Devolvemos la distancia mínima y la ruta
    return distancias.get(fin, float('inf')), ruta

# Ejecución del algoritmo para encontrar el camino más corto desde A hasta G
costo, ruta = dijkstra(grafo, 'A', 'G')
print("Costo mínimo:", costo)
print("Ruta más corta:", " -> ".join(ruta))