Caminos más Cortos

Dijkstra: caminos desde un origen

Para grafos con pesos no negativos. Encuentra el camino más corto desde un nodo a todos los demás.

Analogía: Eres un explorador con un mapa. Siempre expandes la ciudad más cercana que aún no hayas visitado, como una mancha de aceite que se expande por el camino más barato.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<long long, int> pli;  // {distancia, nodo}
const long long INF = 1e18;
const int MAXN = 100005;

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

void dijkstra(int origen, int n) {
    fill(dist, dist + n + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;  // min-heap

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

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

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

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

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijkstra(s, n);

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

Complejidad: $O((V + E) \log V)$

Bellman-Ford: pesos negativos permitidos

Funciona con pesos negativos y detecta ciclos negativos.

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

long long dist[MAXN];

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

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

    // Detectar ciclo negativo
    for (auto &[u, v, w] : aristas) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            return true;  // Hay ciclo negativo
        }
    }

    return false;
}

Complejidad: $O(V \times E)$

Floyd-Warshall: todos contra todos

Encuentra la distancia más corta entre todos los pares de nodos. Ideal para grafos pequeños ($n \leq 500$).

long long dist[505][505];

void floydWarshall(int n) {
    // Inicializar: dist[i][j] = peso de arista o INF
    for (int i = 1; i <= n; i++) 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]);
                }
            }
        }
    }
}

Complejidad: $O(n^3)$

Idea: Para cada nodo intermedio $k$, verifica si pasar por $k$ mejora el camino de $i$ a $j$.

¿Cuál usar?

Ejercicio de práctica

Dado un grafo ponderado no dirigido, encuentra la distancia más corta del nodo 1 al nodo N.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<long long, int> pli;
const long long INF = 1e18;
vector<pair<int,int>> adj[100005];
long long dist_arr[100005];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    fill(dist_arr, dist_arr + n + 1, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dist_arr[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist_arr[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist_arr[u] + w < dist_arr[v]) {
                dist_arr[v] = dist_arr[u] + w;
                pq.push({dist_arr[v], v});
            }
        }
    }

    cout << (dist_arr[n] == INF ? -1 : dist_arr[n]) << endl;
    return 0;
}