Grafos/Dijkstra

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