import heapq
import numpy as np
class GrafoDirigido:
def __init__(self):
self.adyacencia = {}
def agregar_nodo(self, nodo):
self.adyacencia.setdefault(nodo, [])
def agregar_arista(self, origen, destino, peso=1):
if origen in self.adyacencia and destino in self.adyacencia:
self.adyacencia[origen].append((destino, peso))
def mostrar_lista_adyacencia(self):
for nodo, aristas in self.adyacencia.items():
print(f"{nodo}: {aristas}")
def mostrar_matriz_adyacencia(self):
nodos = list(self.adyacencia)
n = len(nodos)
matriz = np.zeros((n, n), dtype=int)
for origen, destinos in self.adyacencia.items():
i = nodos.index(origen)
for destino, peso in destinos:
matriz[i, nodos.index(destino)] = peso
print(" ", " ".join(nodos))
for nodo, fila in zip(nodos, matriz):
print(nodo, " ", " ".join(map(str, fila)))
def dijkstra(self, inicio):
distancias = {nodo: float('inf') for nodo in self.adyacencia}
distancias[inicio] = 0
pq, padres = [(0, inicio)], {nodo: None for nodo in self.adyacencia}
while pq:
distancia_actual, nodo_actual = heapq.heappop(pq)
for vecino, peso in self.adyacencia[nodo_actual]:
nueva_distancia = distancia_actual + peso
if nueva_distancia < distancias[vecino]:
distancias[vecino] = nueva_distancia
padres[vecino] = nodo_actual
heapq.heappush(pq, (nueva_distancia, vecino))
return distancias, padres
def mostrar_camino_mas_corto(self, inicio, fin):
distancias, padres = self.dijkstra(inicio)
if distancias[fin] == float('inf'):
print(f"No hay camino de {inicio} a {fin}")
return
camino, nodo_actual = [], fin
while nodo_actual:
camino.insert(0, nodo_actual)
nodo_actual = padres[nodo_actual]
print(f"Camino más corto de {inicio} a {fin}: {' -> '.join(camino)} con un coste de {distancias[fin]}")
# Ejemplo de uso
grafo = GrafoDirigido()
for nodo in ['A', 'B', 'C', 'D']:
grafo.agregar_nodo(nodo)
for origen, destino, peso in [('A', 'B', 1), ('A', 'C', 4), ('B', 'C', 2), ('B', 'D', 5), ('C', 'D', 1)]:
grafo.agregar_arista(origen, destino, peso)
grafo.mostrar_lista_adyacencia()
grafo.mostrar_matriz_adyacencia()
grafo.mostrar_camino_mas_corto('A', 'D')
