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)) # Para grafos no dirigidos
def dijkstra(self, inicio):
distancias = {nodo: float('inf') for nodo in self.adj_list}
distancias[inicio] = 0
heap = [(0, inicio)] # (distancia, nodo)
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
heapq.heappush(heap, (nueva_distancia, vecino))
return distancias
# Ejemplo de uso:
g = Grafo()
# Agregar nodos
for nodo in range(5):
g.agregar_nodo(nodo)
# Agregar aristas (grafo no dirigido)
g.agregar_arista(0, 1, 2)
g.agregar_arista(0, 2, 3)
g.agregar_arista(1, 3, 4)
g.agregar_arista(2, 4, 5)
g.agregar_arista(3, 4, 1)
# Calcular distancias desde el nodo 0 usando Dijkstra
distancias = g.dijkstra(0)
print(distancias)
