Caminhos mínimos

No grafo abaixo, a ligação direta de $s$ a $a$ custa 4, mas passar por $b$ custa $1+2=3$. O custo de um caminho é a soma dos pesos das suas arestas. Para encontrar o mínimo, mantemos distâncias provisórias e melhoramo-las quando descobrimos uma alternativa mais curta.

A possibilidade de fixar uma distância depende das hipóteses sobre os pesos. Dijkstra exige pesos não negativos e fixa cada vértice uma vez. Num DAG, a ordem topológica permite também pesos negativos, porque todos os antecessores já foram processados. A secção sobre Bellman-Ford mostra por que a ausência de ciclo negativo não chega para salvar Dijkstra.

Relaxação e predecessores

Inicializamos $d[s]=0$ e $d[v]=+\infty$ para os outros vértices. Relaxar a aresta $u\to v$ de peso $w$ significa testar se

Se melhorar, atribuímos $d[v]=d[u]+w$ e pai[v]=u. Só fazemos a soma quando $d[u]$ é finito. Cada valor finito é o custo de algum caminho já encontrado, ou seja é um limite superior para a distância mínima verdadeira. A relaxação melhora esse limite, mas não certifica sozinha que ele já é ótimo.

Para reconstruir $s\to t$, seguimos os pais a partir de $t$ e invertemos a sequência. Um destino inalcançável não tem caminho. A origem tem o caminho de zero arestas. Atualizar apenas em melhoria estrita evita alterações desnecessárias em empates e ajuda a manter a cadeia de pais.

Dijkstra

Dijkstra exige pesos não negativos. Mantém vértices definitivos e escolhe sempre o não definitivo com menor distância provisória. Quando escolhe $u$, a sua distância passa a definitiva. Depois relaxa as arestas que saem de $u$.

Por que pode fixá-la? Considera um caminho mínimo para $u$ e o primeiro vértice $y$ desse caminho que ainda não é definitivo. O predecessor de $y$ já foi processado e relaxou a entrada em $y$. Como todos os pesos são não negativos, o restante caminho até $u$ tem custo não negativo. Como Dijkstra escolheu $u$ antes de $y$, temos $d[u]\le d[y]\le\delta(s,u)$. Como $d[u]$ é o custo de um caminho concreto, a desigualdade oposta também vale. Logo $d[u]=\delta(s,u)$.

O ponto onde a prova usa a hipótese é o passo “o restante caminho tem custo não negativo”. Com uma aresta negativa, esse restante pode reduzir o custo e $d[y]$ pode ainda descer abaixo de $d[u]$ depois de $u$ estar fixado. É esse o erro que as dúvidas sobre Dijkstra com pesos negativos costumam revelar.

O caminho mínimo para $t$ é $s,b,a,c,t$, custo 7. A entrada antiga de $a$ com distância 4 pode continuar na heap, por isso ignora-a quando sair.

O programa usa vértices 0 a n-1. Lê n m origem destino, depois arestas dirigidas u v peso. Rejeita pesos negativos, aceita pesos zero e arestas paralelas. Os limites declarados são 2000 vértices, 20000 arestas e pesos até um milhão.

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

int main() {
    int n, m, s, t;
    if (!(std::cin >> n >> m >> s >> t) || n < 1 || n > 2000 ||
        m < 0 || m > 20000 || s < 0 || s >= n || t < 0 || t >= n) {
        std::cout << "entrada invalida\n";
        return 0;
    }
    using Aresta = std::pair<int, int>;
    std::vector<std::vector<Aresta>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        if (!(std::cin >> u >> v >> w) || u < 0 || u >= n || v < 0 ||
            v >= n || w < 0 || w > 1000000) {
            std::cout << "entrada invalida\n";
            return 0;
        }
        adj[u].push_back({v, w});
    }
    constexpr long long INF = 1LL << 60;
    std::vector<long long> dist(n, INF);
    std::vector<int> pai(n, -1);
    using Entrada = std::pair<long long, int>;
    std::priority_queue<Entrada, std::vector<Entrada>, std::greater<Entrada>> heap;
    dist[s] = 0;
    heap.push({0, s});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w >= dist[v]) continue;
            dist[v] = d + w;
            pai[v] = u;
            heap.push({dist[v], v});
        }
    }
    if (dist[t] == INF) {
        std::cout << "sem caminho\n";
        return 0;
    }
    std::cout << "distancia " << dist[t] << "\ncaminho";
    std::vector<int> caminho;
    for (int v = t; v != -1; v = pai[v]) caminho.push_back(v);
    std::reverse(caminho.begin(), caminho.end());
    for (int v : caminho) std::cout << ' ' << v;
    std::cout << '\n';
}

Com m=0 e origem diferente do destino, devolve sem caminho.

Uma heap com uma entrada por vértice e decreaseKey dá $O((n+m)\log n)$. A variante publicada pode criar $O(m)$ entradas e custa $O(n+m\log(m+1))$ tempo e $O(n+m)$ memória, incluindo a heap e o grafo. Para grafos simples é comum expressar o tempo como $O((n+m)\log n)$. Com matriz e escolha linear do mínimo, o custo é $O(n^2)$.

Pesos negativos e Bellman-Ford

Bellman-Ford aceita pesos negativos. Relaxa todas as arestas repetidamente, no máximo $n-1$ passagens. Após a passagem $k$, todos os caminhos com até $k$ arestas já foram contemplados, embora a implementação in-place possa já ter usado mais do que $k$ arestas dentro da mesma passagem quando processa as arestas por uma ordem favorável. Com arestas $s\to a$ de peso 1 e $a\to b$ de peso 1 nessa ordem, uma só passagem já põe $d[b]=2$, que não é a distância mínima com no máximo uma aresta. A garantia correta é por camadas: se leres apenas a camada anterior em cada passagem, a passagem $k$ dá exatamente os melhores caminhos com até $k$ arestas. Se não há ciclos negativos alcançáveis, um caminho mínimo pode ser simples e ter no máximo $n-1$ arestas. Esta é a razão do limite de passagens.

Para o grafo anterior, se a ordem das arestas for $s\to a$, $b\to a$, $s\to b$, a primeira passagem produz $(d[a],d[b])=(2,5)$ e a segunda produz $(1,5)$. Uma terceira não muda nada, por isso podemos terminar mais cedo quando uma passagem não faz alterações.

Faz ainda uma passagem de diagnóstico. Se uma aresta com origem alcançável continua a melhorar, há um ciclo negativo alcançável de $s$. Os vértices desse ciclo e os que ele alcança não têm distância mínima finita: dar mais voltas diminui o custo sem limite. Um ciclo negativo numa componente inalcançável não afeta o problema dessa origem.

O custo é $O(nm)$ tempo e $O(n)$ memória auxiliar. Para assinalar todos os destinos afetados, recolhe os vértices melhoráveis e percorre as suas saídas. Não devolvas uma cadeia de predecessores como caminho mínimo quando ela pode atravessar o ciclo negativo.

Caminhos num DAG

Num DAG, processa os vértices em ordem topológica e relaxa as saídas de cada um. Quando chega a vez de $v$, todos os possíveis predecessores já foram processados, por isso $d[v]$ já é final, mesmo com pesos negativos.

Ordenação e relaxações custam $O(n+m)$. Vértices anteriores à origem na ordem podem permanecer inalcançáveis; as suas saídas não devem produzir somas com infinito. O método é também programação dinâmica sobre um DAG.

Floyd-Warshall

Para todos os pares, define $D^{(k)}[i,j]$ como o menor custo usando apenas vértices $1,\ldots,k$ como intermédios. Os extremos $i$ e $j$ não ficam sujeitos a essa restrição. Inicializa com infinito, põe zero na diagonal e incorpora cada aresta pelo mínimo entre o valor atual e o seu peso. Assim preservas o menor peso paralelo e uma autoaresta negativa, que já é um ciclo negativo.

Um melhor caminho ou não usa $k$, ou divide-se em $i\to k$ e $k\to j$. Assim,

O ciclo de $k$ deve ser o exterior, para conservar o significado do estado. Sem ciclos negativos, podemos atualizar a mesma matriz. O custo é $\Theta(n^3)$ tempo e $\Theta(n^2)$ espaço.

Com $a\to b=4$, $b\to c=-2$, $a\to c=5$, $c\to a=3$, começamos com

Permitir $a$ cria $c\to b=7$; permitir $b$ melhora $a\to c$ para 2; permitir $c$ cria $b\to a=1$. A matriz final é

Para reconstruir, guarda next[i][j], o primeiro passo de $i$ para $j$. Numa melhoria através de $k$, atribui next[i][j] = next[i][k]. Um par infinito continua sem caminho. Se no fim $D[k,k]<0$, há um ciclo negativo. Todo o par com $i\leadsto k$ e $k\leadsto j$ é afetado; as entradas numéricas calculadas para esses pares não representam distâncias mínimas finitas.

Se só queremos alcançabilidade, a mesma estrutura dá o fecho transitivo: troca mínimo por OU e soma por E. Inicializar a diagonal a verdadeiro inclui caminhos de comprimento zero.

Johnson

Johnson calcula todos os pares num grafo esparso, admitindo arestas negativas mas rejeitando ciclos negativos. Não podemos somar uma constante a cada aresta: caminhos com mais arestas seriam penalizados mais vezes, podendo trocar a ordem dos custos.

Acrescenta uma origem $q$ com arestas de peso zero para todos os vértices. Corre Bellman-Ford e define os potenciais $h(v)=\delta(q,v)$. Se detetar ciclo negativo, termina. Caso contrário, transforma cada peso em

Como $h(v)\le h(u)+w(u,v)$, temos $w'(u,v)\ge0$. Num caminho de $s$ a $t$, os potenciais internos cancelam-se, pelo que $w'(P)=w(P)+h(s)-h(t)$. Todos os caminhos com os mesmos extremos recebem a mesma diferença, conservando o caminho mínimo.

Corre Dijkstra a partir de cada origem com $w'$ e recupera

No exemplo $a\to b=-2$, $b\to c=3$, $a\to c=4$, a origem nova $q$ tem arestas zero para os três vértices. Bellman-Ford dá $h(a)=0$, $h(b)=-2$ pelo caminho $q,a,b$, e $h(c)=0$ pela ligação direta $q\to c$. Os outros caminhos até $c$ custam 4 e 1, por isso não melhoram esse zero.

Dijkstra encontra $\delta'(a,c)=1$ por $a,b,c$. Como os potenciais dos extremos são iguais, recuperar dá $1-0+0=1$. Para $b\to c$, os valores já diferem: a distância transformada é 1, mas a original é $1-(-2)+0=3$. O peso transformado serve para executar Dijkstra; a recuperação devolve a unidade de custo original.

Com heap binário e decreaseKey, a complexidade é $O(nm+n(n+m)\log n)$, incluindo Bellman-Ford e as $n$ execuções de Dijkstra. A matriz de respostas ocupa $\Theta(n^2)$, mesmo que o grafo seja esparso. Johnson é mais adequado a grafos esparsos; Floyd-Warshall oferece uma implementação direta com custo cúbico.