Grafos AvanzadosgrafosDijkstraBellman-FordFloyd-Warshallcamino-corto

Algoritmos de Camino Más Corto

Domina Dijkstra, Bellman-Ford y Floyd-Warshall para encontrar caminos más cortos en grafos

OOI Oaxaca9 de febrero de 20266 min read

Resumen de algoritmos

Algoritmo	Uso	Complejidad	Pesos negativos
BFS	Sin pesos / peso 1	$O(V + E)$	N/A
Dijkstra	Una fuente, pesos ≥ 0	$O((V+E) \log V)$	❌
Bellman-Ford	Una fuente, cualquier peso	$O(VE)$	✅
Floyd-Warshall	Todas las parejas	$O(V^3)$	✅

Dijkstra

El algoritmo más usado para caminos más cortos desde una fuente.

Implementación con priority_queue

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = 1e18;

vector<pair<int, long long>> adj[MAXN];  // {vecino, peso}
long long dist[MAXN];

void dijkstra(int inicio, int n) {
    fill(dist, dist + n + 1, INF);

    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;

    dist[inicio] = 0;
    pq.push({0, inicio});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;  // Ya encontramos algo mejor

        for (auto [v, peso] : adj[u]) {
            if (dist[u] + peso < dist[v]) {
                dist[v] = dist[u] + peso;
                pq.push({dist[v], v});
            }
        }
    }
}

Reconstruir el camino

int padre[MAXN];

void dijkstraConCamino(int inicio, int n) {
    fill(dist, dist + n + 1, INF);
    fill(padre, padre + n + 1, -1);

    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> pq;

    dist[inicio] = 0;
    pq.push({0, inicio});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, peso] : adj[u]) {
            if (dist[u] + peso < dist[v]) {
                dist[v] = dist[u] + peso;
                padre[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

vector<int> obtenerCamino(int destino) {
    if (dist[destino] == INF) return {};

    vector<int> camino;
    for (int v = destino; v != -1; v = padre[v]) {
        camino.push_back(v);
    }
    reverse(camino.begin(), camino.end());
    return camino;
}

Bellman-Ford

Funciona con pesos negativos y detecta ciclos negativos.

struct Arista {
    int u, v;
    long long peso;
};

const long long INF = 1e18;
long long dist[MAXN];

bool bellmanFord(int inicio, int n, vector<Arista>& aristas) {
    fill(dist, dist + n + 1, INF);
    dist[inicio] = 0;

    // Relajar n-1 veces
    for (int i = 0; i < n - 1; i++) {
        for (auto& e : aristas) {
            if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.peso;
            }
        }
    }

    // Verificar ciclo negativo (una iteración más)
    for (auto& e : aristas) {
        if (dist[e.u] < INF && dist[e.u] + e.peso < dist[e.v]) {
            return false;  // Hay ciclo negativo
        }
    }

    return true;  // Sin ciclo negativo
}

Encontrar nodos en ciclo negativo

int padre[MAXN];

int encontrarCicloNegativo(int n, vector<Arista>& aristas) {
    fill(dist, dist + n + 1, 0);  // Empezar todos en 0
    fill(padre, padre + n + 1, -1);

    int nodoEnCiclo = -1;

    for (int i = 0; i < n; i++) {
        nodoEnCiclo = -1;
        for (auto& e : aristas) {
            if (dist[e.u] + e.peso < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.peso;
                padre[e.v] = e.u;
                nodoEnCiclo = e.v;
            }
        }
    }

    if (nodoEnCiclo == -1) return -1;  // Sin ciclo

    // Retroceder n veces para asegurar estar en el ciclo
    for (int i = 0; i < n; i++) {
        nodoEnCiclo = padre[nodoEnCiclo];
    }

    return nodoEnCiclo;
}

Floyd-Warshall

Encuentra distancias entre todos los pares de nodos.

const long long INF = 1e18;
long long dist[505][505];

void floydWarshall(int n) {
    // dist[i][j] ya inicializado con pesos (INF si no hay arista)
    // dist[i][i] = 0

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Reconstruir camino

int siguiente[505][505];

void floydWarshallConCamino(int n) {
    // Inicializar
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && dist[i][j] < INF) {
                siguiente[i][j] = j;
            } else {
                siguiente[i][j] = -1;
            }
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    siguiente[i][j] = siguiente[i][k];
                }
            }
        }
    }
}

vector<int> obtenerCamino(int u, int v) {
    if (siguiente[u][v] == -1) return {};

    vector<int> camino = {u};
    while (u != v) {
        u = siguiente[u][v];
        camino.push_back(u);
    }
    return camino;
}

Detectar ciclo negativo con Floyd

bool tieneCicloNegativo(int n) {
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

0-1 BFS

Para grafos con pesos 0 o 1, más eficiente que Dijkstra:

void bfs01(int inicio, int n) {
    fill(dist, dist + n + 1, INF);

    deque<int> dq;
    dist[inicio] = 0;
    dq.push_front(inicio);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto [v, peso] : adj[u]) {
            if (dist[u] + peso < dist[v]) {
                dist[v] = dist[u] + peso;
                if (peso == 0) {
                    dq.push_front(v);  // Peso 0 al frente
                } else {
                    dq.push_back(v);   // Peso 1 al final
                }
            }
        }
    }
}

Comparación práctica

// Cuándo usar cada algoritmo:

// BFS: Sin pesos o todos peso 1
// Ejemplo: Laberinto, casillas de ajedrez
if (sinPesos) usarBFS();

// Dijkstra: Pesos no negativos, una fuente
// Ejemplo: Mapa de carreteras, redes
if (pesosPositivos && unaFuente) usarDijkstra();

// Bellman-Ford: Puede haber pesos negativos
// Ejemplo: Intercambio de divisas, arbitraje
if (pesosNegativos && unaFuente) usarBellmanFord();

// Floyd-Warshall: Todas las parejas
// Ejemplo: n ≤ 500, múltiples consultas
if (todasParejas && n <= 500) usarFloyd();

Template: Dijkstra

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long INF = 1e18;

vector<pair<int, long long>> adj[MAXN];
long long dist[MAXN];

void dijkstra(int s, int n) {
    fill(dist, dist + n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        // adj[b].push_back({a, c});  // Si es no dirigido
    }

    dijkstra(1, n);

    for (int i = 1; i <= n; i++) {
        cout << (dist[i] == INF ? -1 : dist[i]) << " ";
    }
    cout << "\n";

    return 0;
}