O Algoritmo de Dijkstra em Python: Encontrando o caminho mais curto
- #Python
O Algoritmo de Dijkstra é um método utilizado para encontrar o caminho mais curto entre dois pontos em um conjunto de pontos (grafo) que possuem diferentes distâncias entre eles. Ele foi desenvolvido pelo cientista da computação holandês Edsger Dijkstra em 1956.
Imagine que você está de férias com um super carro alugado e temos um mapa com várias cidades interligadas por estradas, onde cada estrada tem um comprimento associado. Você quer economizar tempo e visitar o maior número de cidades possível, então o objetivo é encontrar o caminho mais curto entre duas cidades quaisquer. O algoritmo de Dijkstra nos ajuda a encontrar essa rota de forma eficiente.
Como esse algoritmo funciona? Vamos usar o exemplo do mapa com as cidades e apesar de parecer complicado da primeira vez, se torna bem intuitivo depois, vamos lá!
- Inicialmente, atribuímos uma distância infinita entre todas as cidades, exceto para a cidade de partida que terá distância zero, já que você já está nela 😄 Isso representa que ainda não temos informações sobre as distâncias reais entre as cidades.
- Selecionamos a cidade de partida e "visitamos" no mapa 👀 todas as suas cidades vizinhas. Atualizamos as distâncias para essas cidades vizinhas, considerando o comprimento das estradas.
- Em seguida, selecionamos a cidade com a menor distância atual entre todas as cidades não visitadas e repetimos o processo de atualização das distâncias para suas cidades vizinhas.
- Continuamos selecionando e explorando as cidades com as menores distâncias até que todas as cidades tenham sido visitadas ou até chegarmos à cidade de destino.
- Ao final do algoritmo, teremos a menor distância entre a cidade de partida e todas as outras cidades, bem como o caminho mais curto para cada cidade.
Para tentar dar mais visibilidade aos passos acima, vamos aplicar esse conceito em um exemplo prático:
Imagine que temos cinco pontos (ou cidades): A, B, C, D e E, e queremos encontrar o caminho mais curto de A para todos os outros pontos. Cada ponto é representado por uma cidade no mapa, e as conexões entre as cidades têm distâncias associadas.
Usando o algoritmo de Dijkstra, iniciamos com a cidade "A" como ponto de partida e calculamos as distâncias para as cidades vizinhas conectadas a cidade "A" por estradas ("B", "C" e "D"). Em seguida, selecionamos a cidade com a menor distância e repetimos o processo até visitarmos todas as cidades.
No exemplo fornecido, a saída do algoritmo de Dijkstra seria:
- Distância de A para A: 0 (caminho mais curto é A)
- Distância de A para B: 5 (caminho mais curto é A -> C -> B)
- Distância de A para C: 3 (caminho mais curto é A -> C)
- Distância de A para D: 2 (caminho mais curto é A -> D)
- Distância de A para E: 8 (caminho mais curto é A -> D -> E)
Essas informações nos ajudam a entender quais cidades estão mais próximas de A e qual é a rota mais curta para cada uma delas.
O Algoritmo de Dijkstra tem várias aplicações práticas, como roteamento de redes, sistemas de navegação e otimização de caminhos em geral.
Espero que essa explicação inicial ajude você a compreender o conceito do Algoritmo de Dijkstra.
Agora podemos prosseguir com o exemplo prático em Python que mencionamos anteriormente.
import sys
# Função do algoritmo de Dijkstra
def calcular_dijkstra(grafo, origem):
# Inicialização das distâncias com infinito, exceto a origem que é zero
distancias = {v: sys.maxsize for v in grafo}
distancias[origem] = 0
# Conjunto de vértices visitados
visitados = set()
while visitados != set(distancias):
# Encontra o vértice não visitado com menor distância atual
vertice_atual = None
menor_distancia = sys.maxsize
for v in grafo:
if v not in visitados and distancias[v] < menor_distancia:
vertice_atual = v
menor_distancia = distancias[v]
# Marca o vértice atual como visitado
visitados.add(vertice_atual)
# Atualiza as distâncias dos vértices vizinhos
for vizinho, peso in grafo[vertice_atual].items():
if distancias[vertice_atual] + peso < distancias[vizinho]:
distancias[vizinho] = distancias[vertice_atual] + peso
# Retorna as distâncias mais curtas a partir da origem
return distancias
# Definindo o grafo com as conexões e custos
grafo = {
'A': {'B': 5, 'C': 3, 'D': 2},
'B': {'A': 5, 'C': 2, 'E': 4},
'C': {'A': 3, 'B': 2, 'D': 1},
'D': {'A': 2, 'C': 1, 'E': 7},
'E': {'B': 4, 'D': 7}
}
# Ponto de partida
origem = 'A'
# Chamando o algoritmo de Dijkstra para encontrar os caminhos mais curtos a partir de A
caminhos_mais_curto = dijkstra(grafo, origem)
# Exibindo os caminhos mais curtos
for destino, distancia in caminhos_mais_curto.items():
print(f"Caminho mais curto de {origem} para {destino}: {distancia}")s
Agora, passo a explicar cada bloco de código:
- Importamos o módulo sys para utilizar o valor de infinito (sys.maxsize) na inicialização das distâncias.
- Definimos a função dijkstra que implementa o algoritmo de Dijkstra. Essa função recebe o grafo e o vértice de origem como parâmetros.
- Inicializamos as distâncias para todos os vértices como infinito, exceto para o vértice de origem que é definido como zero.
- Criamos um conjunto visitados para armazenar os vértices já visitados.
- Entramos em um loop que continua até visitarmos todos os vértices.
- Encontramos o vértice não visitado com a menor distância atual. Percorremos todos os vértices e verificamos se eles não estão em visitados e se a distância atual é menor que a menor distância encontrada até o momento.
- Marcamos o vértice atual como visitado, adicionando-o ao conjunto visitados.
- Atualizamos as distâncias dos vértices vizinhos do vértice atual. Percorremos todos os vizinhos e verificamos se a soma da distância atual do vértice atual com o peso da aresta para o vizinho é menor que a distância atual do vizinho. Se for, atualizamos a distância.
- Retornamos o dicionário distancias com as distâncias mais curtas a partir da origem.
- Definimos o grafo com as conexões e custos entre os vértices.
- Escolhemos o ponto de partida, que nesse caso é o vértice 'A'.
- Chamamos a função dijkstra passando o grafo e a origem como parâmetros, e armazenamos o resultado na variável caminhos_mais_curto.
- Finalmente, percorremos o dicionário caminhos_mais_curto e exibimos os caminhos mais curtos a partir da origem para cada destino.
Executando o código acima, você obterá a seguinte saída:
Caminho mais curto de A para A: 0
Caminho mais curto de A para B: 5
Caminho mais curto de A para C: 3
Caminho mais curto de A para D: 2
Caminho mais curto de A para E: 8
Espero que esse exemplo prático, com explicações passo a passo, ajude a visualizar como o algoritmo de Dijkstra pode ser aplicado na prática para encontrar os caminhos mais curtos entre pontos. Se tiver mais alguma dúvida ou se precisar de mais esclarecimentos, fique à vontade para perguntar.
Espero que este conteúdo tenha ajudado você e caso queira aprofundar os estudos e testar na prática o algoritmo, criei um treinamento bem simplificado que inclui exercícios hands-on (mão na massa) e até um ambiente de teste gratuito para você brincar com o algoritmo.
Se quiser me adicionar no LinkedIn posso ajudar com qualquer dúvida que surgir. Segue o link do artigo por lá:
https://www.linkedin.com/pulse/o-algoritmo-de-dijkstra-encontrando-caminho-mais-curto-carlos-herrera
