Translate

Resolução de Problemas por Meio de Buscas

🗺️ 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:

  1. Define a cidade inicial com distância zero e todas as outras com infinito.

  2. Usa uma fila de prioridade para sempre explorar a cidade com menor custo atual.

  3. Atualiza as distâncias para os vizinhos se encontrar um caminho mais barato.

  4. 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! 🚀

 

Postado por