D´Esopo-Pape

Dado um grafo com $n$ vértices e $m$ arestas com pesos $w_i$ e um vértice inicial $v_0$. A tarefa é encontrar o caminho mais curto do vértice $v_0$ para todos os outros vértices.

O algoritmo de D´Esopo-Pape funcionará mais rápido que o algoritmo de Dijkstra e o de Bellman-Ford na maioria dos casos, e também funcionará para arestas negativas. No entanto, não para ciclos negativos.

Descrição

Deixe a array $d$ conter os menores comprimentos de caminho, ou seja: $d_i$ é o comprimento atual do caminho mais curto do vértice $v_0$ para o vértice $i$. Inicialmente, essa array é preenchida com "infinito" para cada vértice, exceto para o vértice inicial: $d_{v_0} = 0$. Após a conclusão do algoritmo, essa array conterá as menores distâncias.

Deixe a array $p$ conter os ancestrais atuais, ou seja: $p_i$ é o ancestral direto do vértice $i$ no caminho mais curto atual de $v_0$ a $i$. Assim como a array $d$, a array $p$ muda gradualmente durante o algoritmo e no final assume seus valores finais.

Agora para o algoritmo. Em cada etapa, três conjuntos de vértices são mantidos:

Os vértices no conjunto $M_1$ são armazenados em uma queue bidirecional (deque).

Em cada etapa do algoritmo, pegamos um vértice do conjunto $M_1$ (da frente da queue). Seja $u$ o vértice selecionado. Colocamos esse vértice $u$ no conjunto $M_0$. Em seguida, iteramos sobre todas as arestas que saem desse vértice. Seja $v$ o segundo extremo(final) da aresta atual e $w$ seu peso.

E, é claro, a cada atualização na array $d$ também precisamos atualizar o elemento correspondente na array $p$.

Implementação

Usaremos uma array $m$ para armazenar em que conjunto cada vértice está atualmente.

struct Edge {  //aresta
    int to, w;
};

int n;
vector<vector<Edge>> adj;  //lista de adjacência - grafo

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);
                }
            }
        }
    }
}

Complexidade

O algoritmo geralmente tem uma performance muito rápida. Na maioria dos casos, ainda mais rápida que o algoritmo de Dijkstra. No entanto, existem casos em que o algoritmo leva tempo exponencial.