Tarea conjunta de programacion y matematica discreta - Pablo Bronée.py

class Grafo:
    def __init__(self, num_nodos):
        # Inicializa el número inicial de nodos y la matriz de adyacencia
        self.num_nodos = num_nodos
        self.matriz_adyacencia = [[float('inf')] * num_nodos for _ in range(num_nodos)]
        
        # Inicializa la diagonal principal a 0 (distancia de un nodo a si mismo es 0)
        for i in range(num_nodos):
            self.matriz_adyacencia[i][i] = 0

    def agregar_nodo(self):
        # Incrementa el número de nodos
        self.num_nodos += 1
        
        # Agrega una nueva fila con valores "inf" para el nuevo nodo
        for fila in self.matriz_adyacencia:
            fila.append(float('inf'))
        
        # Agrega una nueva columna con valores "inf" para el nuevo nodo
        nueva_fila = [float('inf')] * self.num_nodos
        nueva_fila[-1] = 0  # La distancia del nodo a sí mismo es 0
        self.matriz_adyacencia.append(nueva_fila)

    def agregar_arista(self, nodo1, nodo2, peso):
        # Establece el peso de la arista entre nodo1 y nodo2 en la matriz de adyacencia
        self.matriz_adyacencia[nodo1][nodo2] = peso

    def mostrar_matriz_adyacencia(self):
        # Imprime la matriz de adyacencia, reemplazando "inf" por "X" para mayor claridad
        print("Matriz de adyacencia:")
        for fila in self.matriz_adyacencia:
            fila_mostrada = ['X' if valor == float('inf') else valor for valor in fila]
            print(fila_mostrada)

    def dijkstra(self, nodo_inicial):
        # Inicializa las distancias y nodos visitados
        distancias = [float('inf')] * self.num_nodos
        distancias[nodo_inicial] = 0
        visitados = [False] * self.num_nodos

        for _ in range(self.num_nodos):
            # Encuentra el nodo con la menor distancia que aún no ha sido visitado
            min_dist = float('inf')
            min_nodo = -1
            for nodo in range(self.num_nodos):
                if not visitados[nodo] and distancias[nodo] < min_dist:
                    min_dist = distancias[nodo]
                    min_nodo = nodo

            # Marca el nodo como visitado
            visitados[min_nodo] = True

            # Actualiza las distancias a los nodos adyacentes
            for nodo_adyacente in range(self.num_nodos):
                if (self.matriz_adyacencia[min_nodo][nodo_adyacente] != float('inf') and 
                    not visitados[nodo_adyacente]):
                    nueva_distancia = distancias[min_nodo] + self.matriz_adyacencia[min_nodo][nodo_adyacente]
                    if nueva_distancia < distancias[nodo_adyacente]:
                        distancias[nodo_adyacente] = nueva_distancia

        # Imprime los resultados
        self.mostrar_resultados(nodo_inicial, distancias)

    def mostrar_resultados(self, nodo_inicial, distancias):
        # Imprime las distancias calculadas desde el nodo inicial a cada nodo
        print(f"Distancias desde el nodo {nodo_inicial}:")
        for nodo in range(self.num_nodos):
            if distancias[nodo] == float('inf'):
                print(f"Distancia a nodo {nodo}: X")
            else:
                print(f"Distancia a nodo {nodo}: {distancias[nodo]}")

# Ejemplo de uso
grafo = Grafo(5)

grafo.agregar_arista(0, 1, 7)
grafo.agregar_arista(0, 4, 3)
grafo.agregar_arista(1, 3, 6)
grafo.agregar_arista(2, 3, 2)
grafo.agregar_arista(3, 4, 8)
grafo.agregar_arista(1, 2, 4)
grafo.agregar_arista(4, 2, 5)

grafo.mostrar_matriz_adyacencia()
grafo.dijkstra(0)

# Ahora se agrega un nuevo nodo y luego se muestra la matriz adyacente nuevamente
print("\nDespués de agregar un nuevo nodo:")
grafo.agregar_nodo()
grafo.mostrar_matriz_adyacencia()