🗺️ Encontrando o Caminho Mais Rápido Entre Cidades com o Algoritmo de Dijkstra
Analisemos o exemplo da Figura a seguir: os nós são cidades, são os estados deste espaço, sendo que Cidade 1 é o estado inicial e a Cidade 7 é o estado final. As outras cidades são estados parciais ou intermediários na solução do problema. Os arcos são caminhos que especificam a distância em quilômetros entre duas cidades. Neste grafo poderíamos acrescentar – nos arcos – os nomes das estradas e as direções ou sentidos.
Imagine que você está planejando uma viagem entre cidades conectadas por estradas, e deseja saber qual é o caminho mais rápido para chegar ao seu destino. Como resolver isso de forma eficiente, mesmo com várias possibilidades de rota? 🤔
A resposta está em um dos algoritmos mais clássicos e poderosos da ciência da computação: o algoritmo de Dijkstra.
Neste post, vamos mostrar como aplicamos esse algoritmo a um grafo representando cidades e estradas, onde cada conexão tem um custo (tempo de viagem). Vamos usar Python para isso, e no final, teremos não só o caminho mais curto, mas também os pontos intermediários por onde passamos.
🚦 O Problema
Dado um conjunto de cidades e estradas com tempos de deslocamento entre elas, queremos:
✅ Encontrar o caminho de menor custo entre duas cidades
✅ Saber o tempo total da viagem
✅ Identificar quais cidades intermediárias fazem parte do trajeto
🧮 Representando o Grafo
As cidades são os vértices e as estradas com seus tempos (em minutos) são as arestas ponderadas. Por exemplo:
grafo = {
'Cidade 1': {'Cidade 2': 10, 'Cidade 6': 220, 'Cidade 7': 400},
'Cidade 2': {'Cidade 1': 10, 'Cidade 4': 100, 'Cidade 6': 230},
'Cidade 3': {'Cidade 4': 30, 'Cidade 5': 20},
'Cidade 4': {'Cidade 2': 100, 'Cidade 3': 30, 'Cidade 7': 120},
'Cidade 5': {'Cidade 3': 20, 'Cidade 6': 85, 'Cidade 7': 45},
'Cidade 6': {'Cidade 1': 220, 'Cidade 2': 230, 'Cidade 5': 85},
'Cidade 7': {'Cidade 4': 120, 'Cidade 5': 45, 'Cidade 1': 400}
}
🚀 O Algoritmo de Dijkstra
O algoritmo funciona assim:
-
Define a cidade inicial com distância zero e todas as outras com infinito.
-
Usa uma fila de prioridade para sempre explorar a cidade com menor custo atual.
-
Atualiza as distâncias para os vizinhos se encontrar um caminho mais barato.
-
No final, reconstrói o caminho mais curto com base nos predecessores de cada cidade.
Confira a implementação completa em Python:
import heapq
def dijkstra(grafo, inicio, fim):
distancias = {v: float('infinity') for v in grafo}
distancias[inicio] = 0
predecessores = {v: None for v in grafo}
fila = [(0, inicio)]
while fila:
atual_dist, atual = heapq.heappop(fila)
if atual_dist > distancias[atual]:
continue
for vizinho, peso in grafo[atual].items():
nova_dist = atual_dist + peso
if nova_dist < distancias[vizinho]:
distancias[vizinho] = nova_dist
predecessores[vizinho] = atual
heapq.heappush(fila, (nova_dist, vizinho))
caminho = []
atual = fim
while atual is not None:
caminho.insert(0, atual)
atual = predecessores[atual]
if distancias[fim] == float('infinity'):
return "Caminho não encontrado", float('infinity')
return caminho, distancias[fim]
🔍 Exemplo na Prática
Vamos calcular o menor caminho de Cidade 1 até Cidade 7:
caminho, custo = dijkstra(grafo, 'Cidade 1', 'Cidade 7')
print("Caminho:", caminho)
print("Custo total:", custo)
🧭 Resultado:
Caminho: ['Cidade 1', 'Cidade 2', 'Cidade 4', 'Cidade 3', 'Cidade 5', 'Cidade 7']
Custo total: 205
Os pontos intermediários (excluindo início e fim) são:
['Cidade 2', 'Cidade 4', 'Cidade 3', 'Cidade 5']
🧠 Por que isso é útil?
Esse tipo de solução tem aplicações em:
-
Sistemas de navegação (como Waze e Google Maps)
-
Planejamento logístico
-
Redes de computadores (roteamento)
-
Inteligência Artificial e Jogos
🔗 Conclusão
O algoritmo de Dijkstra é uma ferramenta essencial para encontrar caminhos mínimos em grafos com pesos positivos. E com uma simples implementação em Python, conseguimos resolver um problema de mundo real de forma elegante e eficiente.
Se você curte algoritmos e quer continuar explorando grafos, IA e otimização, siga nosso blog e deixe seu comentário! 🚀
