actividad de Dijkstra.

import heapq

class Grafo:
    def __init__(self):
        self.adj_list = {}

    def agregar_nodo(self, nodo):
        if nodo not in self.adj_list:
            self.adj_list[nodo] = []

    def agregar_arista(self, origen, destino, peso):
        self.adj_list[origen].append((destino, peso))
        self.adj_list[destino].append((origen, peso))  # Grafo no dirigido

    def dijkstra(self, inicio):
        distancias = {nodo: float('inf') for nodo in self.adj_list}
        distancias[inicio] = 0
        heap = [(0, inicio)]  # (distancia, nodo)
        predecesores = {nodo: None for nodo in self.adj_list}

        while heap:
            dist_actual, nodo_actual = heapq.heappop(heap)

            if dist_actual > distancias[nodo_actual]:
                continue

            for vecino, peso in self.adj_list[nodo_actual]:
                nueva_distancia = dist_actual + peso

                if nueva_distancia < distancias[vecino]:
                    distancias[vecino] = nueva_distancia
                    predecesores[vecino] = nodo_actual
                    heapq.heappush(heap, (nueva_distancia, vecino))

        return distancias, predecesores

    def mostrar_camino(self, predecesores, destino):
        camino = []
        while destino is not None:
            camino.append(destino)
            destino = predecesores[destino]
        return camino[::-1]  # Invertir el camino

# Ejemplo basado en la imagen proporcionada:
g = Grafo()

# Agregar nodos
for nodo in ['A', 'B', 'C', 'D', 'E', 'F', 'G']:
    g.agregar_nodo(nodo)

# Agregar aristas según la tabla de la imagen
g.agregar_arista('A', 'B', 30)
g.agregar_arista('A', 'C', 90)
g.agregar_arista('B', 'C', 72)
g.agregar_arista('B', 'D', 30)
g.agregar_arista('B', 'E', 48)
g.agregar_arista('C', 'D', 120)
g.agregar_arista('C', 'F', 150)
g.agregar_arista('C', 'G', 180)
g.agregar_arista('D', 'E', 100)
g.agregar_arista('D', 'G', 60)
g.agregar_arista('E', 'F', 150)
g.agregar_arista('F', 'G', 72)

# Ejecutar el algoritmo de Dijkstra desde 'A'
distancias, predecesores = g.dijkstra('A')

# Mostrar distancias
print("Distancias más cortas desde A:")
for nodo in distancias:
    print(f"Distancia a {nodo}: {distancias[nodo]}")

# Mostrar el camino más corto desde 'A' hasta 'G'
camino = g.mostrar_camino(predecesores, 'G')
print("\nEl camino más corto desde A hasta G es:", " -> ".join(camino))
print(f"El costo mínimo es: {distancias['G']}")