# Caminhos mínimos

Relaxação, Dijkstra, Bellman-Ford, DAG, Floyd-Warshall e Johnson, com condições e reconstrução.

Página: https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/

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

$$
d[u]+w<d[v].
$$

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.

![Grafo dirigido com s a peso 4, s b peso 1, b a peso 2, b c peso 5, a c peso 1 e c t peso 3.](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/figura-1.svg)

| Vértice fixado | $d[a]$ | $d[b]$ | $d[c]$ | $d[t]$ |
| --- | --- | --- | --- | --- |
| $s$ | 4 | 1 | $\infty$ | $\infty$ |
| $b$ | 3 | 1 | 6 | $\infty$ |
| $a$ | 3 | 1 | 4 | $\infty$ |
| $c$ | 3 | 1 | 4 | 7 |
| $t$ | 3 | 1 | 4 | 7 |

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.

**main.cpp**

```cpp
#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

Sem ciclo negativo não basta para Dijkstra

No grafo $s\to a$ de peso 2, $s\to b$ de peso 5 e $b\to a$ de peso $-4$, Dijkstra fixa $a$ com 2 antes de processar $b$. A distância correta é 1. Não há ciclo negativo: uma única aresta negativa já destrói a prova de Dijkstra.

[Animação: Uma distância fixada cedo demais](https://resumos.rgo.pt/manim/da-aresta-negativa/a26d3e371205dc97/feup-light-red.mp4)

**Uma distância fixada cedo demais.** Dijkstra fixa a com custo 2 antes de processar b. A aresta de peso −4 revela depois o caminho de custo 1; Bellman-Ford permite rever essa distância.

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,

$$
D^{(k)}[i,j]=\min\left(D^{(k-1)}[i,j],D^{(k-1)}[i,k]+D^{(k-1)}[k,j]\right).
$$

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

$$
D^{(0)}=\begin{pmatrix}0&4&5\\\infty&0&-2\\3&\infty&0\end{pmatrix}.
$$

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 é

$$
D=\begin{pmatrix}0&4&2\\1&0&-2\\3&7&0\end{pmatrix}.
$$

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

$$
w'(u,v)=w(u,v)+h(u)-h(v).
$$

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

$$
\delta(s,t)=\delta'(s,t)-h(s)+h(t).
$$

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.

| Aresta | Peso original | Transformação | Peso novo |
| --- | --- | --- | --- |
| $a\to b$ | $-2$ | $-2+0-(-2)$ | 0 |
| $b\to c$ | 3 | $3+(-2)-0$ | 1 |
| $a\to c$ | 4 | $4+0-0$ | 4 |

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.

## Exercícios

Escolher algoritmo com uma aresta negativa

Há arestas dirigidas s→a=3, s→b=7 e b→a=-6. Não há outras. Calcula a distância de s a a e explica por que Dijkstra não tem garantia nesta entrada. Indica dois métodos válidos.

Pista

Compara o caminho direto com o que passa por b.

Mais uma pista

7-6=1. O grafo é um DAG, além de não ter ciclos negativos.

Solução

A distância é 1 pelo caminho s,b,a. Dijkstra pode fixar a com 3 antes de retirar b com 7; a aresta negativa permite uma melhoria tardia que a prova excluía. Bellman-Ford é válido, e relaxar em ordem topológica s,b,a também é válido e custa O(n+m). Não há ciclo negativo, mas a hipótese de Dijkstra já falha.

Confere a tua resposta:

*   Calculei distância 1 e o caminho.
*   Expliquei a fixação prematura de a.
*   Indiquei Bellman-Ford e ordem topológica.

Erros frequentes

Verificar apenas ausência de ciclos negativos não basta para Dijkstra. Uma BFS contaria arestas e também resolveria outro objetivo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/#pesos-negativos-e-bellman-ford)

Melhorar através de um intermediário

As únicas arestas são a→b de peso 6, b→c de peso -2 e a→c de peso 5. Qual é a distância de a a c depois de permitir b como intermediário em Floyd-Warshall?

Pista

Compara a entrada atual com D\[a,b\]+D\[b,c\].

Solução

A distância passa de 5 para 4 pelo caminho a,b,c. O estado compara não usar b com usá-lo entre os extremos. O grafo não tem ciclos negativos; os pares sem caminho continuam infinitos. A soma só se calcula se as duas parcelas forem finitas.

Erros frequentes

Minimizar pesos de arestas isoladas sem somar o caminho não é relaxação. Não somes o sentinela de infinito com um peso negativo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/#floyd-warshall)

Pesos novos e distância original

As únicas arestas são $a\to b=-2$, $b\to c=3$ e $a\to c=4$. Os potenciais são $h(a)=0$, $h(b)=-2$ e $h(c)=0$. Calcula os três pesos reponderados e a distância **original de b a c** a partir da transformada. Explica por que a transformação conserva a ordem dos caminhos com os mesmos extremos.

Pista

Os extremos b e c têm potenciais diferentes.

Solução

Os pesos novos são $-2+0-(-2)=0$, $3-2-0=1$ e $4+0-0=4$. De b a c só há o caminho direto, com distância transformada 1. Recuperar dá $1-h(b)+h(c)=1-(-2)+0=3$.

Num caminho, cada potencial interior aparece com os dois sinais e cancela-se. Só sobra $h(s)-h(t)$, a mesma diferença para todos os caminhos entre os mesmos extremos. Devolver 1 confundiria distância transformada com original.

Confere a tua resposta:

*   Obtive pesos 0, 1, 4.
*   Recuperei distância original 3 de b a c.
*   Expliquei o cancelamento dos potenciais.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/#johnson)