import numpy as np class Grafo: def __init__(self, num_nodos): # Inicializa la matriz de adyacencia con infinitos usando NumPy self.num_nodos = num_nodos self.matriz_adyacencia = np.full((num_nodos, num_nodos), float('inf')) # La distancia de cada nodo a sí mismo es 0 np.fill_diagonal(self.matriz_adyacencia, 0) def agregar_nodo(self): # Incrementa el número de nodos y redimensiona la matriz self.num_nodos += 1 nueva_matriz = np.full((self.num_nodos, self.num_nodos), float('inf')) nueva_matriz[:self.num_nodos-1, :self.num_nodos-1] = self.matriz_adyacencia np.fill_diagonal(nueva_matriz, 0) self.matriz_adyacencia = nueva_matriz def agregar_arista(self, origen, destino, peso): # Agrega una arista con peso entre los nodos origen y destino if origen < self.num_nodos and destino < self.num_nodos: self.matriz_adyacencia[origen, destino] = peso else: print("Error: El nodo especificado no existe.") def mostrar_matriz(self): # Imprime la matriz de adyacencia print(self.matriz_adyacencia) def dijkstra(self, origen): distancias = np.full(self.num_nodos, float('inf')) distancias[origen] = 0 visitado = np.full(self.num_nodos, False) camino = np.full(self.num_nodos, -1) for _ in range(self.num_nodos): # Selecciona el nodo no visitado con la menor distancia u = np.argmin(np.where(visitado, float('inf'), distancias)) visitado[u] = True # Actualiza las distancias de los nodos adyacentes for v in range(self.num_nodos): if self.matriz_adyacencia[u, v] != float('inf') and not visitado[v]: nueva_distancia = distancias[u] + self.matriz_adyacencia[u, v] if nueva_distancia < distancias[v]: distancias[v] = nueva_distancia camino[v] = u # Muestra el resultado for destino in range(self.num_nodos): if distancias[destino] == float('inf'): print(f"No hay camino de {origen} a {destino}.") else: # Reconstruye el camino desde el nodo origen al destino ruta = [] actual = destino while actual != -1: ruta.insert(0, actual) actual = camino[actual] print(f"Camino más corto de {origen} a {destino}: {ruta} con costo {distancias[destino]}") # Crear un grafo con 4 nodos grafo = Grafo(4) # Agregar aristas con peso grafo.agregar_arista(0, 1, 2) grafo.agregar_arista(0, 2, 4) grafo.agregar_arista(1, 2, 1) grafo.agregar_arista(2, 3, 3) # Mostrar la matriz de adyacencia print("Matriz de Adyacencia:") grafo.mostrar_matriz() # Ejecutar el algoritmo de Dijkstra desde el nodo 0 print("\nCamino más corto desde el nodo 0:") grafo.dijkstra(0)