Caminhos Mínimos

2026-07-26 intermediario matematica-discreta, teoria-dos-grafos algoritmos, redes, otimizacao

Caminhos Mínimos

Encontrar o caminho de menor custo entre dois pontos é um dos problemas mais aplicados da computação. A escolha do algoritmo depende de três perguntas: os pesos podem ser negativos? Preciso de uma origem ou de todos os pares? O grafo é denso ou esparso?

O problema

Dado $G = (V, E)$ com pesos $w: E \to \mathbb{R}$, o custo de um caminho é a soma dos pesos das arestas. Busca-se o caminho de custo mínimo.

Três variantes:

Origem única: de um vértice a todos.
Todos os pares: entre quaisquer dois.
Par único: entre dois vértices dados. Na prática resolve-se com o algoritmo de origem única, possivelmente com parada antecipada.

Se houver ciclo de peso negativo alcançável, não existe caminho mínimo: dar voltas no ciclo reduz o custo indefinidamente. Detectar esses ciclos é parte do problema.

A operação de relaxamento

Todos os algoritmos compartilham uma única operação. Mantendo uma estimativa $d[v]$ do custo até $v$:

def relaxa(u, v, w, d, pai):
    if d[u] + w[u][v] < d[v]:
        d[v] = d[u] + w[u][v]
        pai[v] = u

Os algoritmos diferem apenas na ordem em que relaxam as arestas. Entender isso simplifica muito: não são três ideias diferentes, é uma ideia com três estratégias de ordenação.

Dijkstra

Estratégia gulosa: sempre expandir o vértice não visitado de menor distância estimada.

import heapq

def dijkstra(grafo, origem):
    dist = {v: float('inf') for v in grafo}
    dist[origem] = 0
    fila = [(0, origem)]
    visto = set()
    while fila:
        d, u = heapq.heappop(fila)
        if u in visto:
            continue
        visto.add(u)
        for v, peso in grafo[u]:
            if dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso
                heapq.heappush(fila, (dist[v], v))
    return dist

Exige pesos não negativos. A prova de correção depende de que, ao extrair o vértice de menor estimativa, essa estimativa já seja definitiva — e um peso negativo mais adiante poderia reduzi-la depois, quebrando o argumento.

Complexidade: $O((V+E)\log V)$ com heap binário; $O(E + V\log V)$ com heap de Fibonacci.

Bellman-Ford

Relaxa todas as arestas $|V|-1$ vezes.

def bellman_ford(vertices, arestas, origem):
    dist = {v: float('inf') for v in vertices}
    dist[origem] = 0
    for _ in range(len(vertices) - 1):
        for u, v, peso in arestas:
            if dist[u] + peso < dist[v]:
                dist[v] = dist[u] + peso
    # uma passada extra detecta ciclo negativo
    for u, v, peso in arestas:
        if dist[u] + peso < dist[v]:
            raise ValueError('ciclo de peso negativo alcançável')
    return dist

Aceita pesos negativos e detecta ciclos negativos. O número de iterações vem do fato de que um caminho mínimo tem no máximo $|V|-1$ arestas; se ainda houver melhoria na passada extra, existe ciclo negativo.

Complexidade: $O(VE)$ — mais lento, em troca de generalidade.

Floyd-Warshall

Programação dinâmica para todos os pares:

def floyd_warshall(dist, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

A ideia: $k$ percorre os vértices permitidos como intermediários. Após a iteração $k$, dist[i][j] é o mínimo usando apenas ${0,\dots,k}$ como intermediários.

Complexidade $\Theta(V^3)$, espaço $\Theta(V^2)$. Vale a pena em grafos densos e pequenos. Valor negativo na diagonal indica ciclo negativo.

Comparação

Algoritmo	Alcance	Pesos negativos	Complexidade	Quando usar
BFS	Origem única	Sem pesos	$O(V+E)$	Grafo não ponderado
Dijkstra	Origem única	Não	$O(E \log V)$	Padrão para pesos positivos
Bellman-Ford	Origem única	Sim	$O(VE)$	Há pesos negativos
Floyd-Warshall	Todos os pares	Sim	$O(V^3)$	Grafo denso e pequeno
A*	Par único	Não	Depende da heurística	Há boa estimativa de distância

Se o grafo não é ponderado, use BFS: ela resolve em tempo linear o que Dijkstra resolveria com um fator logarítmico a mais.

A*: Dijkstra com heurística

A* ordena a fila por $f(v) = d[v] + h(v)$, com $h$ uma estimativa do custo restante até o destino.

Para garantir otimalidade, $h$ precisa ser admissível (nunca superestimar) e, para a versão com conjunto fechado, consistente ($h(u) \le w(u,v) + h(v)$).

Com $h \equiv 0$, A* é exatamente Dijkstra. Quanto melhor a heurística, menos nós são expandidos. Em mapas, a distância em linha reta é admissível e reduz drasticamente a exploração — é o que torna viável o roteamento em grafos rodoviários continentais.

Exemplo trabalhado

Grafo dirigido: $A \to B$ (peso 4), $A \to C$ (2), $C \to B$ (1), $B \to D$ (5), $C \to D$ (8).

Dijkstra a partir de $A$:

Extrai $A$ ($d=0$). Relaxa: $d[B]=4$, $d[C]=2$.
Extrai $C$ ($d=2$, menor). Relaxa: $d[B] = \min(4, 2+1) = 3$; $d[D] = 10$.
Extrai $B$ ($d=3$). Relaxa: $d[D] = \min(10, 3+5) = 8$.
Extrai $D$ ($d=8$).

Resultado: $A \to C \to B \to D$ com custo $8$. Note que o caminho ótimo passa por $C$ mesmo a aresta direta $A \to B$ existindo — é exatamente o tipo de situação que o relaxamento captura.

Aplicações em computação

Roteamento. OSPF usa Dijkstra; RIP e BGP usam variantes de vetor de distância aparentadas com Bellman-Ford.

Navegação. Mapas usam A* com pré-processamento (rotulagem de atalhos, hierarquias de contração) para responder em milissegundos sobre grafos com milhões de vértices.

Arbitragem. Um ciclo de peso negativo sobre $-\log(\text{taxa de câmbio})$ é uma oportunidade de arbitragem — Bellman-Ford detecta.

Jogos. Busca de caminho de unidades em mapa de grade, tipicamente A* com heurística de Manhattan ou octil.

Escalonamento. Restrições de diferença ($x_j - x_i \le c$) formam um sistema resolvido por caminhos mínimos.

Erros comuns

Usar Dijkstra com pesos negativos. O resultado pode estar errado sem nenhum aviso.
Esquecer a passada extra do Bellman-Ford, perdendo a detecção de ciclo negativo.
Não verificar se o vértice já foi visitado ao desempilhar em Dijkstra, degradando o desempenho.
Heurística inadmissível em A*, que produz caminho subótimo silenciosamente.
Floyd-Warshall com $V$ grande. $V = 10^4$ já significa $10^{12}$ operações.

Leituras recomendadas

Cormen et al., capítulos 24 e 25 — caminhos mínimos com provas de correção completas.
Kleinberg e Tardos, capítulo 6 — Bellman-Ford apresentado como programação dinâmica.
Documentação do NetworkX e do igraph — implementações de referência e escolha de algoritmo por caso.
Artigos sobre hierarquias de contração — como o roteamento em mapas reais fica rápido o suficiente.

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058. Jon Kleinberg and Eva Tardos (2005). Algorithm Design. Pearson. ISBN 9780321295354.

Referências

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.
Jon Kleinberg; Eva Tardos (2005). Algorithm Design. Pearson.