GafoWhitDijkstra.cs

using System;
using System.Collections.Generic;
using static Debug; 
using static Macros.Utils; 
class Edge{
    public char A, B;
    public int Cost;
    public Edge(char a, char b, int cost){
        A = a;
        B = b;
        Cost = cost;
    }
}

class Program{
    static int Dijkstra(List<Edge> edges, char begin, char end){
        var map = new Dictionary<char, int>();
        var reverseMap = new Dictionary<int, char>();
        int index = 0;
        foreach (var edge in edges){
            if (!map.ContainsKey(edge.A)){
                map[edge.A] = index;
                reverseMap[index] = edge.A;
                index++;
            }
            if (!map.ContainsKey(edge.B)){
                map[edge.B] = index;
                reverseMap[index] = edge.B;
                index++;
            }
        }

        int n = map.Count;
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++)
            adj[i] = new List<(int, int)>();

        foreach (var edge in edges){
            adj[map[edge.A]].Add((map[edge.B], edge.Cost));  // Grafo dirigido
        }

        int[] dist = new int[n];
        int[] prev = new int[n];
        for (int i = 0; i < n; i++){
            dist[i] = int.MaxValue;
            prev[i] = -1;
        }

        dist[map[begin]] = 0;
        var pq = new SortedSet<(int dist, int node)>(Comparer<(int, int)>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1 - b.Item1 : a.Item2 - b.Item2));

        pq.Add((0, map[begin]));

        while (pq.Count > 0){
            var (currentDist, u) = pq.Min;
            pq.Remove(pq.Min);

            if (u == map[end])
                break;

            foreach (var (v, cost) in adj[u]){
                int newDist = currentDist + cost;
                if (newDist < dist[v]){
                    pq.Remove((dist[v], v));
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.Add((newDist, v));
                }
            }
        }

        PrintShortestPath(prev, map[begin], map[end], reverseMap, dist[map[end]]);
        return dist[map[end]];
    }

    static void PrintShortestPath(int[] prev, int begin, int end, Dictionary<int, char> reverseMap, int cost){
        var path = new Stack<int>();
        for (int at = end; at != -1; at = prev[at])
            path.Push(at);
        debug("Camino más corto: ");
        if (path.Peek() != begin){
            debug("No se encontró ningún camino");
        }
        else{
            while (path.Count > 1)
                Console.Write(reverseMap[path.Pop()] + " -> ");
                Console.WriteLine(reverseMap[path.Pop()]);
                debug("Costo total: " + cost);
        }
    }

    static void FindAllPaths(List<Edge> edges, char begin, char end, int shortestPathCost){
        var graph = new Dictionary<char, List<(char, int)>>();

        foreach (var edge in edges){
            if (!graph.ContainsKey(edge.A)){
                graph[edge.A] = new List<(char, int)>();
            }
            graph[edge.A].Add((edge.B, edge.Cost));
        }

        var visited = new HashSet<char>();
        var path = new List<char>();
        int pathCost = 0;

        DFS(graph, begin, end, visited, path, ref pathCost, shortestPathCost);
    }

    static void DFS(Dictionary<char, List<(char, int)>> graph, char current, char end, HashSet<char> visited, List<char> path, ref int pathCost, int shortestPathCost){
        visited.Add(current);
        path.Add(current);

        if (current == end){
            if (pathCost != shortestPathCost){
                debug("Ruta: " + string.Join(" -> ", path) + " | Costo: " + pathCost);
            }
        }
        else if (graph.ContainsKey(current)){
            foreach (var (next, cost) in graph[current]){
                if (!visited.Contains(next)){
                    pathCost += cost;
                    DFS(graph, next, end, visited, path, ref pathCost, shortestPathCost);
                    pathCost -= cost;
                }
            }
        }

        path.RemoveAt(path.Count - 1);
        visited.Remove(current);
    }

    static void Main(){
        Console.Write("Ingrese el número de aristas: ");
        int edgeCount = Convert.ToInt32(Console.ReadLine());
        var edges = new List<Edge>();

        for (int i = 0; i < edgeCount; i++){
            Console.Write("Ingrese la arista (formato: A B 1, donde A y B son nodos y 1 es el costo): ");
            string[] input = Console.ReadLine().Split(' ');
            char nodeA = input[0][0];
            char nodeB = input[1][0];
            int cost = Convert.ToInt32(input[2]);
            edges.Add(new Edge(nodeA, nodeB, cost));
        }
        
        Console.Write("Ingrese el nodo de inicio: ");
        char begin = Console.ReadLine()[0];

        Console.Write("Ingrese el nodo de destino: ");
        char end = Console.ReadLine()[0];

        // Implementar Dijkstra para encontrar el camino más corto
        int shortestPathCost = Dijkstra(edges, begin, end);

        // Encontrar y mostrar todos los caminos alternativos
        Console.WriteLine("\nCaminos alternativos:");
        FindAllPaths(edges, begin, end, shortestPathCost);
    }
}