Tarea grafo
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
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)
Python
INFO