programacionI - Gonzalo Perrone

import sys

class Grafo:
    def __init__(self, num_nodos):
        self.num_nodos = num_nodos
        self.matriz_adyacencia = [[0] * num_nodos for _ in range(num_nodos)]
        self.nodos = {i: chr(65 + i) for i in range(num_nodos)}

    def agregar_arista(self, origen, destino, peso):
        if 0 <= origen < self.num_nodos and 0 <= destino < self.num_nodos:
            self.matriz_adyacencia[origen][destino] = peso

    def mostrar_matriz(self):
        print("Matriz de adyacencia:")
        for fila in self.matriz_adyacencia:
            print(fila)
        print()

    def dijkstra(self, inicio):
        distancias = [sys.maxsize] * self.num_nodos
        distancias[inicio] = 0
        visitados = [False] * self.num_nodos
        predecesores = [-1] * self.num_nodos

        for _ in range(self.num_nodos):
            nodo_actual = min((dist for dist in range(self.num_nodos) if not visitados[dist]), key=distancias.__getitem__)
            visitados[nodo_actual] = True

            for vecino, peso in enumerate(self.matriz_adyacencia[nodo_actual]):
                if peso > 0 and not visitados[vecino] and distancias[nodo_actual] + peso < distancias[vecino]:
                    distancias[vecino] = distancias[nodo_actual] + peso
                    predecesores[vecino] = nodo_actual

        self.mostrar_resultado(distancias, predecesores, inicio)

    def mostrar_resultado(self, distancias, predecesores, inicio):
        print(f"Desde el nodo {self.nodos[inicio]}:")
        for destino in range(self.num_nodos):
            if destino != inicio:
                camino = self.construir_camino(predecesores, destino)
                print(f"Hasta {self.nodos[destino]}: {' -> '.join(camino)}, Costo: {distancias[destino]}")

    def construir_camino(self, predecesores, destino):
        camino = []
        while destino != -1:
            camino.insert(0, self.nodos[destino])
            destino = predecesores[destino]
        return camino

# Ejemplo de uso
grafo = Grafo(5)
grafo.agregar_arista(0, 1, 10)
grafo.agregar_arista(0, 4, 3)
grafo.agregar_arista(1, 2, 2)
grafo.agregar_arista(2, 3, 9)
grafo.agregar_arista(4, 1, 4)
grafo.agregar_arista(4, 2, 8)
grafo.mostrar_matriz()
grafo.dijkstra(0)