Algoritmo de D´Esopo-Pape

Dado un grafo con $n$ vértices y $m$ aristas con pesos $w_i$ y un vértice de inicio $v_0$. La tarea es encontrar el camino más corto del vértice $v_0$ a cada otro vértice.

El algoritmo de D´Esopo-Pape suele trabajar más rápido que el algoritmo de Dijkstra y el algoritmo de Bellman-Ford en la mayoría de los casos, y también funciona con aristas negativas. Sin embargo no para ciclos negativos.

Descripción

Sea el arreglo $d$ el que contiene las longitudes de los caminos más cortos, es decir, $d_i$ es la longitud actual del camino más corto del vértice $v_0$ al vértice $i$. Inicialmente este arreglo se llena con infinito para cada vértice, excepto $d_{v_0} = 0$. Cuando el algoritmo termina, este arreglo contendrá las distancias más cortas.

Sea el arreglo $p$ el que contiene los ancestros actuales, es decir, $p_i$ es el ancestro directo del vértice $i$ en el camino más corto actual de $v_0$ a $i$. Al igual que el arreglo $d$, el arreglo $p$ cambia gradualmente durante el algoritmo y al final toma sus valores finales.

Ahora al algoritmo. En cada paso se mantienen tres conjuntos de vértices:

• $M_0$ - vértices para los cuales la distancia ya se calculó (aunque podría no ser la distancia final)
• $M_1$ - vértices para los cuales la distancia se está calculando actualmente
• $M_2$ - vértices para los cuales la distancia todavía no se calculó

Los vértices del conjunto $M_1$ se guardan en una cola bidireccional (deque).

En cada paso del algoritmo tomamos un vértice del conjunto $M_1$ (del frente de la cola). Sea $u$ el vértice seleccionado. Ponemos este vértice $u$ en el conjunto $M_0$. Después iteramos sobre todas las aristas que salen de este vértice. Sea $v$ el otro extremo de la arista actual, y $w$ su peso.

• Si $v$ pertenece a $M_2$, entonces $v$ se inserta en el conjunto $M_1$ insertándolo al final de la cola. $d_v$ se pone en $d_u + w$.
• Si $v$ pertenece a $M_1$, entonces intentamos mejorar el valor de $d_v$: $d_v = \min(d_v, d_u + w)$. Como $v$ ya está en $M_1$, no hace falta insertarlo en $M_1$ ni en la cola.
• Si $v$ pertenece a $M_0$, y si $d_v$ se puede mejorar $d_v > d_u + w$, entonces mejoramos $d_v$ e insertamos el vértice $v$ de vuelta al conjunto $M_1$, colocándolo al principio de la cola.

Y por supuesto, con cada actualización en el arreglo $d$ también hay que actualizar el elemento correspondiente en el arreglo $p$.

Implementación

Usaremos un arreglo $m$ para guardar en qué conjunto está actualmente cada vértice.

struct Edge {
    int to, w;
};

int n;
vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                } else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}

Complejidad

El algoritmo suele ser bastante rápido: en la mayoría de los casos, incluso más rápido que el algoritmo de Dijkstra. Sin embargo existen casos para los cuales el algoritmo toma tiempo exponencial, lo que lo hace inadecuado en el peor caso. Ver discusiones en Stack Overflow  y Codeforces  como referencia.