import heapq # Heapq se utiliza para usar colas de prioridad import numpy as np # Numpy permite manejar matrices de manera eficiente class GrafoDirigido: def __init__(self): self.adyacencia = {} # Diccionario para la lista de adyacencia def agregar_nodo(self, nodo): #Agrega un nodo al grafo. self.adyacencia.setdefault(nodo, []) # Inicializa una lista vacía para el nodo si no existe def agregar_arista(self, origen, destino, peso=1): #Agrega una arista dirigida con un peso (por defecto 1) al grafo. if origen in self.adyacencia and destino in self.adyacencia: self.adyacencia[origen].append((destino, peso)) # Añade el destino y peso a la lista de adyacencia def mostrar_lista_adyacencia(self): #Muestra la lista de adyacencia del grafo. for nodo, aristas in self.adyacencia.items(): print(f"{nodo}: {aristas}") def generar_matriz_adyacencia(self): #Genera una matriz de adyacencia a partir de la lista de adyacencia. nodos = list(self.adyacencia) n = len(nodos) matriz = np.zeros((n, n), dtype=int) # Inicializa una matriz n x n llena de ceros for origen, destinos in self.adyacencia.items(): i = nodos.index(origen) for destino, peso in destinos: j = nodos.index(destino) matriz[i, j] = peso # Asigna el peso en la posición correcta return matriz, nodos def mostrar_matriz_adyacencia(self): #Muestra la matriz de adyacencia del grafo. matriz, nodos = self.generar_matriz_adyacencia() # Genera la matriz de adyacencia print(" ", " ".join(nodos)) # Imprime los nombres de los nodos como cabecera for nodo, fila in zip(nodos, matriz): print(nodo, " ", " ".join(map(str, fila))) # Imprime cada fila de la matriz def dijkstra(self, inicio): #Implementa el algoritmo de Dijkstra para encontrar el camino más corto desde el nodo 'inicio'. distancias = {nodo: float('inf') for nodo in self.adyacencia} # Inicializa las distancias como infinito distancias[inicio] = 0 # La distancia al nodo de inicio es 0 pq = [(0, inicio)] # Cola de prioridad inicializada con el nodo de inicio padres = {nodo: None for nodo in self.adyacencia} # Diccionario para almacenar el nodo anterior while pq: distancia_actual, nodo_actual = heapq.heappop(pq) # Extrae el nodo con la menor distancia for vecino, peso in self.adyacencia[nodo_actual]: nueva_distancia = distancia_actual + peso # Calcula la nueva distancia if nueva_distancia < distancias[vecino]: # Si la nueva distancia es menor, actualiza distancias[vecino] = nueva_distancia padres[vecino] = nodo_actual heapq.heappush(pq, (nueva_distancia, vecino)) # Añade el vecino a la cola de prioridad return distancias, padres def mostrar_camino_mas_corto(self, inicio, fin): #Muestra el camino más corto y su costo desde 'inicio' hasta 'fin' usando Dijkstra. distancias, padres = self.dijkstra(inicio) # Ejecuta Dijkstra para obtener las distancias y padres 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) # Reconstruye el camino desde el nodo final al inicio 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 FUNCIONAMIENTO grafo = GrafoDirigido() # Añade nodos al grafo for nodo in ['A', 'B', 'C', 'D']: grafo.agregar_nodo(nodo) # Añade aristas al grafo 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() # Muestra la lista de adyacencia grafo.mostrar_matriz_adyacencia() # Muestra la matriz de adyacencia grafo.mostrar_camino_mas_corto('A', 'D') # Muestra el camino más corto de A a D