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']}")
