Algoritmo de Dijkstra: caminho mínimo passo a passo

O algoritmo de Dijkstra encontra caminhos de menor custo a partir de uma origem em um grafo com pesos não negativos. Ele mantém distâncias provisórias, escolhe o vértice ainda não finalizado de menor distância e tenta melhorar os caminhos para seus vizinhos. O custo mínimo é a soma dos pesos das arestas, que podem representar distância, tempo ou outra medida definida pelo modelo.

O ponto central não é escolher repetidamente a menor aresta disponível. A decisão usa o custo acumulado desde a origem. Este artigo explica a diferença com um exemplo rastreável, apresenta a operação de relaxamento e mostra por que pesos negativos impedem a garantia da versão clássica. Os grafos e custos utilizados são exemplos didáticos originais.

Qual problema Dijkstra resolve

Um grafo reúne vértices e arestas. Em um modelo de deslocamento, vértices podem representar prédios e arestas podem representar trajetos. O peso de uma aresta precisa ter significado consistente: se alguns pesos são minutos e outros são metros, somá-los sem uma transformação explícita não produz um objetivo interpretável.

Em grafos direcionados, uma aresta de A para B não garante a existência do trajeto de B para A. Em grafos não direcionados, a ligação pode ser percorrida nos dois sentidos, conforme o modelo. Definir isso antes da execução evita um erro frequente: encontrar uma rota barata que usa uma ligação no sentido não permitido.

Distâncias, predecessores e relaxamento

Inicialize a distância da origem com zero e as demais com infinito. Infinito significa que nenhum caminho foi descoberto, não que o destino foi provado inacessível. Para registrar a rota, mantenha também um predecessor: o vértice pelo qual o melhor caminho conhecido chega ao destino.

Relaxar uma aresta u → v significa testar se dist[u] + peso(u,v) é menor que dist[v]. Se for, atualize a distância de v e registre u como predecessor. A operação produz uma possibilidade melhor; ela não finaliza automaticamente v. Ainda pode existir outro caminho descoberto posteriormente com custo mais baixo.

Essa distinção entre valor provisório e valor final é essencial. O algoritmo só finaliza o próximo vértice quando ele possui a menor distância provisória entre os candidatos. Em implementações com fila de prioridade, a estrutura organiza essa escolha; em versões simples, uma varredura dos vértices pode cumprir o mesmo papel.

Exemplo de grafo com cinco vértices

Considere um grafo direcionado com origem A e vértices A, B, C, D e E. As arestas são A→B com peso 4, A→C com peso 1, C→B com peso 2, C→D com peso 5, B→D com peso 1, B→E com peso 7 e D→E com peso 3. Todos os pesos são não negativos e usam a mesma unidade de custo.

A ligação direta A→B custa 4. Entretanto, A→C→B custa 1 + 2 = 3. Por isso, encontrar uma aresta direta para um destino não permite declarar que esse é seu menor caminho. A sequência de atualizações deve continuar até que a regra de finalização seja satisfeita.

Execução passo a passo

Registre cada melhoria, inclusive quando um vértice já havia sido descoberto por outro caminho. No exemplo, B passa de 4 para 3, D passa de 6 para 4 e E passa de 10 para 7. Uma solução que marca o vértice como concluído na primeira descoberta pode bloquear precisamente essas melhorias necessárias.

Por que os pesos precisam ser não negativos

A garantia de Dijkstra depende do fato de que continuar um caminho não reduz seu custo acumulado. Com pesos não negativos, uma alternativa ainda não explorada não consegue voltar de uma distância maior para tornar melhor a distância do vértice escolhido. Esse raciocínio sustenta a finalização gulosa, isto é, uma escolha local com garantia global sob as hipóteses do problema.

Considere o contraexemplo A→B com peso 2, A→C com peso 5 e C→B com peso −10. O caminho A→C→B custa −5, mas uma execução que finaliza B com custo 2 não tem a garantia clássica. Não basta dizer que “há poucas arestas negativas” ou que a maioria dos pesos é positiva.

Estruturas de dados e custo computacional

Uma implementação simples pode procurar o menor candidato examinando os vértices, levando tipicamente a O(V²) no caso geral. Com listas de adjacência e uma fila de prioridade baseada em heap binário, uma implementação usual alcança O((V + E) log V). Aqui V é a quantidade de vértices e E é a quantidade de arestas; hipóteses e operações da fila precisam ser especificadas.

O custo também depende da representação. Uma matriz de adjacência ocupa espaço proporcional a V², mesmo quando há poucas conexões. Listas de adjacência representam explicitamente as conexões existentes. Revise estruturas de dados e seus custos para conectar a escolha do algoritmo à organização dos dados.

Algumas versões não diminuem a prioridade de um item já inserido: elas inserem um novo par de distância e vértice. Nesse caso, podem permanecer entradas antigas na fila. Ao removê-las, a implementação deve descartá-las quando já não correspondem à distância atual. Confundir essa estratégia com uma fila sem duplicatas gera análises de tempo e memória inconsistentes.

Como escolher entre Dijkstra, BFS e Bellman–Ford

Se o objetivo é apenas um destino, é possível parar quando ele é finalizado pela regra correta, não quando ele aparece pela primeira vez. Para obter distâncias de uma origem a todos os destinos alcançáveis, continue até esvaziar a fila. Vértices não alcançados permanecem sem caminho registrado; isso não é erro de execução.

Erros de modelagem e como conferir a resposta

Uma aplicação pode estar programada corretamente e resolver o problema errado. Por exemplo, um peso de tempo fixo não representa automaticamente trânsito que varia durante a viagem. Restrições de capacidade, janelas de atendimento e múltiplos objetivos também podem exigir modelos adicionais. Explicite quais características foram traduzidas para o grafo e quais ficaram de fora.

Um exercício pode ser organizado como um pequeno estudo de caso: descreva o cenário, declare o modelo, execute o algoritmo e interprete a solução. Esse registro torna verificável a relação entre necessidade prática e resultado computacional, em vez de apresentar apenas a sequência de letras da rota.

Perguntas frequentes sobre Dijkstra

Dijkstra sempre encontra uma única rota?

Não. Podem existir caminhos diferentes com o mesmo custo mínimo. A ordem de desempate e a política de atualização de predecessores influenciam a rota registrada. O valor mínimo continua correto quando as condições do algoritmo e a implementação são respeitadas.

Ele funciona com peso zero?

Sim. Zero é não negativo. A implementação precisa tratar empates e evitar reconstruções inconsistentes, mas a existência de arestas de custo zero não viola a hipótese fundamental de Dijkstra.

Posso usar Dijkstra com uma aresta negativa?

A versão clássica não oferece a garantia pretendida nesse caso. Analise alternativas adequadas às propriedades do grafo e verifique ciclos negativos. A condição é sobre todos os pesos utilizados, e não sobre a soma final do caminho.