Dijkstra.cpp

#include<cstdio>
#include<cstring>

#include<queue>

#define C(x) ( x > 'Z' ? x-'a' : x-'A' )

typedef unsigned int uint32; //Ahorramos escribir mucho texto asi LoL!...
typedef std::vector<char> t_way; //Ahorramos escribir mucho texto asi LoL!...

// Clase para obtener todas las rutas posibles de un origen a un destino.
class GraphWay
{
public:
    t_way way;
    char lastVertex;
    uint32 currentCost;

    GraphWay(uint32 cost, char currentVertex) :
        lastVertex(currentVertex),
        currentCost(cost) {  // Constructor para el caso inicial.
        way.push_back(currentVertex);
    }

    GraphWay(uint32 cost, char currentVertex, const t_way& currentWay) :
        lastVertex(currentVertex),
        currentCost(cost),
        way(currentWay) { // Constructor que se utilizara cuando se consigue una nueva ruta.
        way.push_back(currentVertex);
    }

    GraphWay(const GraphWay& clone) :
        lastVertex(clone.lastVertex),
        currentCost(clone.currentCost),
        way(clone.way) { } // Constructor de clonado o asignacion.

    bool operator < (const GraphWay& o) const
    {
        // Operador utilizado para que la cola de prioridad entienda cual ruta tiene menor costo y
        // desencolarlo primero.
        return o.currentCost < currentCost;
    }

};

int main() {
    uint32 w, N, i;
    char u, v, source, dest;

    std::priority_queue< GraphWay > pq;

    uint32 G[26][26]; // Matriz de adyacencia
    uint32 minCost[26]; // Arreglo de costo minimo para llegar a un vertice desde el origen.

    //Inicializamos la G en 0 y minCost en Infinito.
    memset(G, 0, sizeof(G));
    memset(minCost, 0xFF, sizeof(minCost));

    //freopen Redirecciona la entrada STD desde un archivo
    if (freopen("input.txt", "r", stdin) == NULL) {
        printf("File not found...");
        return -1;
    }

    // La primera linea me dara el Origen, Destino y la cantidad de aristas del grafo.
    scanf("%c %c %u\n", &source, &dest, &N);

    //Leemos las aristas (Grafo bidireccional)
    for (i = 0; i < N; ++i) {
        if (scanf("%c %c %u\n", &u, &v, &w) == 3) {
            G[C(u)][C(v)] = w;
            G[C(v)][C(u)] = w;
        }
    }

    GraphWay result(0xffffffff, source); //Si no hay un camino, el resutado sera 0xffffffff.

    GraphWay firstElement(0, source);
    pq.push(firstElement);
    minCost[C(source)] = 0; //Inicializamos la cola con el origen y costo 0.

    while (!pq.empty()) { //Vamos buscando siempre el camino con menor costo.
        GraphWay current = pq.top();//Sacamos el camino con menor costo de la cola.
        pq.pop();
        uint32 costAcump = current.currentCost;
        char u = current.lastVertex;
        if (u == dest) { //Si llegamos al destino se termina el algoritmo.
            result = current;
            break;
        }
        for (char v = 'A'; v <= 'H'; ++v) { //Buscamos cual vertice esta conectado con el actual.
            if (G[C(u)][C(v)]) { //Si hay una conexion con el vertice actual verificamos esta nueva ruta.
                uint32 newCost = costAcump + G[C(u)][C(v)]; //Calculamos el costo que tiene esta nueva ruta.
                if (minCost[C(v)] > newCost) {
                    //Si el costo es inferior al ultimo que se utilizo para llegar a este
                    //vertice entonces se reemplaza, en caso contrario se descarta este camino.
                    minCost[C(v)] = newCost; // Nuevo costo del camino encontrado
                    pq.push(GraphWay(newCost, v, current.way)); // Se añade a la cola de prioridad como
                                                                // una nueva ruta potencialmente mejor.
                }
            }
        }
    }

    printf("El menor costo de la ruta es: %u.\nLa ruta final es: ", result.currentCost);
    for (uint32 i = 0; i < result.way.size(); ++i) {
        printf("%c ", result.way[i]);
    }
    printf("\n");
    return 0;
}

input.txt

A H 11
A B 3
A C 1
C F 5
C D 2
F D 2
F H 3
B D 1
B G 5
D E 4
G E 2
E H 2