Integrada

import heapq
import numpy as np

class GrafoDirigido:
    def __init__(self):
        self.adyacencia = {}

    def agregar_nodo(self, nodo):
        self.adyacencia.setdefault(nodo, [])

    def agregar_arista(self, origen, destino, peso=1):
        if origen in self.adyacencia and destino in self.adyacencia:
            self.adyacencia[origen].append((destino, peso))

    def mostrar_lista_adyacencia(self):
        for nodo, aristas in self.adyacencia.items():
            print(f"{nodo}: {aristas}")

    def mostrar_matriz_adyacencia(self):
        nodos = list(self.adyacencia)
        n = len(nodos)
        matriz = np.zeros((n, n), dtype=int)
        for origen, destinos in self.adyacencia.items():
            i = nodos.index(origen)
            for destino, peso in destinos:
                matriz[i, nodos.index(destino)] = peso
        print("  ", " ".join(nodos))
        for nodo, fila in zip(nodos, matriz):
            print(nodo, " ", " ".join(map(str, fila)))

    def dijkstra(self, inicio):
        distancias = {nodo: float('inf') for nodo in self.adyacencia}
        distancias[inicio] = 0
        pq, padres = [(0, inicio)], {nodo: None for nodo in self.adyacencia}

        while pq:
            distancia_actual, nodo_actual = heapq.heappop(pq)
            for vecino, peso in self.adyacencia[nodo_actual]:
                nueva_distancia = distancia_actual + peso
                if nueva_distancia < distancias[vecino]:
                    distancias[vecino] = nueva_distancia
                    padres[vecino] = nodo_actual
                    heapq.heappush(pq, (nueva_distancia, vecino))

        return distancias, padres

    def mostrar_camino_mas_corto(self, inicio, fin):
        distancias, padres = self.dijkstra(inicio)
        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)
            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 uso
grafo = GrafoDirigido()
for nodo in ['A', 'B', 'C', 'D']:
    grafo.agregar_nodo(nodo)
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()
grafo.mostrar_matriz_adyacencia()
grafo.mostrar_camino_mas_corto('A', 'D')