Caminhos mínimos

Relaxação

$d[s]=0$, restantes $+\infty$. Relaxar $u\to v$ testa $d[u]+w<d[v]$ com $d[u]$ finito. Cada valor finito é custo de caminho conhecido, um limite superior. Atualiza predecessor só em melhoria estrita.

Escolher o método

Situação	Método	Hipótese	Custo
Pesos não negativos, uma origem	Dijkstra	Fixa menor provisório; prova usa não negatividade do resto	$O((n+m)\log n)$; denso $O(n^2)$ com matriz
Pesos arbitrários, uma origem	Bellman-Ford	$n-1$ passagens; extra com melhoria denuncia ciclo negativo alcançável	$O(nm)$
DAG, uma origem	Ordem topológica	Todos antecessores antes; admite negativos	$O(n+m)$
Todos os pares, denso	Floyd-Warshall	$k$ exterior; diagonal negativa denuncia ciclo	$\Theta(n^3)$, $\Theta(n^2)$ espaço
Todos os pares, esparso	Johnson	Sem ciclos negativos; repesa com $h$	$O(nm+n(n+m)\log n)$

Condições que decidem

• Dijkstra fixa cedo demais com $s\to a=2$, $s\to b=5$, $b\to a=-4$: fixa 2 e perde 1. Ausência de ciclo negativo não chega.
• Bellman-Ford: $n-1$ passagens contemplam todos os caminhos com até $n-1$ arestas; a versão in-place pode antecipar melhorias na mesma passagem. Uma passagem extra com melhoria desde a origem denuncia ciclo negativo alcançável.
• Ciclo negativo alcançável deixa pares sem mínimo finito; não devolvas cadeia como caminho mínimo.
• DAG: não somes infinito de vértices antes da origem.
• Floyd: $D^{(k)}[i,j]=\min(D^{(k-1)}[i,j],D^{(k-1)}[i,k]+D^{(k-1)}[k,j])$. Inicializa com menor paralelo e autoaresta negativa. Guarda next para reconstruir.
• Johnson: $w'=w+h(u)-h(v)\ge0$ com $h$ de Bellman-Ford desde $q$; recupera $\delta=\delta'-h(s)+h(t)$. Somar constante a todas as arestas não preserva mínimos.

Execução e reconstrução.