Grafos com peso: Dijkstra e BFS

O problema

Tem pergunta de grafo que parece tranquila até aparecer a frase “menor caminho”.

Aí muita gente pega a primeira ferramenta que lembra:

• BFS
• Dijkstra

e torce para encaixar.

O problema é que eles não resolvem exatamente a mesma coisa.

Os dois percorrem um grafo.

Mas o tipo de distância que cada um respeita é diferente.

Modelo mental

BFS pensa em camadas.

Ela é ótima quando sair de um nó para outro sempre custa o mesmo.

Dijkstra pensa em custo acumulado.

Ela é ótima quando cada aresta pode ter um custo diferente, desde que os pesos não sejam negativos.

Em frase curta:

BFS minimiza passos. Dijkstra minimiza custo.

Se passos e custo são a mesma coisa, BFS basta.

Se não são, BFS deixa de ser confiável.

Quebrando o problema

Pergunta 1: o que significa “distância” aqui?

Essa é a pergunta que salva a solução.

Distância pode significar:

• quantidade de arestas
• tempo total
• custo total
• risco total
• energia total

Se a entrevista fala de menor número de saltos e cada salto custa igual, BFS costuma resolver.

Se fala de custo total e cada aresta pode cobrar valor diferente, você saiu do terreno da BFS pura.

Quando BFS funciona

BFS é perfeita quando:

• o grafo é sem peso
• ou todos os pesos são iguais

Por quê?

Porque explorar por camadas preserva o menor número de passos.

A primeira vez que você chega a um nó, você chegou pelo caminho com menos arestas.

Quando Dijkstra entra

Se uma aresta pode custar 1 e outra pode custar 100, “chegar primeiro” deixa de significar “chegar mais barato”.

Agora você precisa sempre expandir o próximo estado com menor custo acumulado até aqui.

É isso que a fila de prioridade faz.

Ela não pergunta “quem entrou antes?”.

Ela pergunta:

Qual caminho está mais barato neste momento?

Peso negativo muda o jogo

Dijkstra assume pesos não negativos.

Se existe peso negativo, a lógica de “o menor custo atual é seguro para expandir agora” deixa de valer.

Em entrevista, só de você perguntar isso cedo já mostra maturidade.

Exemplo simples

Imagine este grafo:

• A -> B com custo 100
• A -> C com custo 1
• C -> B com custo 1

Se a pergunta for “qual caminho usa menos arestas?”, A -> B vence com um passo.

Se a pergunta for “qual caminho tem menor custo total?”, A -> C -> B vence com custo 2.

Esse exemplo desmonta a confusão rápido.

BFS olharia camadas e encontraria B cedo.

Dijkstra olharia custo acumulado e preferiria passar por C.

O papel da estrutura de dados

BFS

Normalmente usa:

• queue
• visited

Você explora por ordem de chegada em camadas.

Dijkstra

Normalmente usa:

• mapa de distâncias
• fila de prioridade ou min-heap

Você pode até visitar o mesmo nó mais de uma vez na fila com custos diferentes.

O importante é consolidar o menor custo válido.

Um erro clássico é marcar visited cedo demais em Dijkstra, como se fosse BFS.

Em geral, o momento seguro para considerar um nó fechado é quando ele sai da min-heap com o menor custo atual conhecido.

Erros comuns

• Usar BFS em grafo ponderado só porque quer “menor caminho”.
• Esquecer que BFS minimiza saltos, não peso.
• Usar Dijkstra com peso negativo.
• Marcar nó como resolvido cedo demais em Dijkstra.
• Tratar fila simples e min-heap como diferença cosmética.

Como um senior pensa

Quem já viu esse tipo de pergunta costuma fazer um corte muito cedo:

• o custo é uniforme ou variável?
• quero menor número de passos ou menor peso total?
• existe peso negativo?

Perceba que isso é mais importante do que lembrar o pseudocódigo inteiro na hora.

Se você escolhe a família de solução certa, o resto fica bem menos caótico.

Se escolhe a família errada, pode codar bonito o quanto quiser que a resposta continua torta.

O que o entrevistador quer ver

Ele quer ver se você:

• entende o que o problema está minimizando
• faz a distinção entre camadas e custo acumulado
• sabe quando BFS basta
• sabe a limitação de Dijkstra

Uma resposta forte costuma começar assim:

“Antes de escolher BFS ou Dijkstra, eu quero confirmar se todas as arestas têm o mesmo custo e se há peso negativo.”

Isso já mostra que você não está escolhendo por reflexo.

Em grafo, “menor caminho” sem definir a métrica ainda não significa nada.

Quando o custo muda, a ordem da exploração também precisa mudar.