Menor caminho - 1
📚 Introdução
O algoritmo de Dijkstra é um algoritmo guloso que encontra o menor caminho entre dois vértices em um grafo com arestas de peso não negativo.
Ele recebe um vértice principal S para ser a fonte do grafo e retorna o menor caminho de todos os vértices do grafo para S.
🤷 Como funciona?
A ideia do algoritmo consiste em:
Definir a distância como ∞ para todos os vértices e como 0 para o vértice S.
Em cada passo, encontrar o vértice u, que ainda não foi processado, que possua a menor das distâncias. Este vértices agora foi fixado como já tendo a menor distância de S para ele.
Ver para cada vértice v, vizinho de u, se é melhor manter a distância atual de v ou atualizar fazendo o caminho
S→u e depois u→v. Repare que o caminho S→u já foi fixado e possivelmente tem conexões no meio.
Vamos entender melhor com um exemplo, observe o seguinte grafo:
Vamos simular o Dijkstra fazendo S=1.
Primeiro, inicializamos as distâncias:
O vértice de menor distância é o 7. Então, selecionamos ele e atualizamos as distâncias dos vértices 3 e 4, que são seus vizinhos.
O novo vértice de menor distância é o 2. Selecionamos então ele e só alteramos a distância do vértice 3 (pois não compensa mudar o 4).
O novo vértice mais próximo é o vértice 4. Com ele, podemos atualizar a distância do vértice 5 e do vértice 3.
O novo vértice mais próximo é o 3, mas não conseguimos mudar nenhuma distância.
O novo vértice mais próximo é o 5, mas também não atualizamos nenhuma distância.
E assim concluímos o algoritmo, tendo calculado a menor distâncida do vértice 1 para qualquer outro vértice, as distâncias finais são:
Repare que não acessamos o 6 nenhuma vez, pois a distância dele ao 1 é infinita, o que significa que não temos como chegar nele, o que é facilmente observado como verdadeiro.
🧠 Exemplo de aplicação
Imagine que você está de férias na europa, mas agora está morrendo de saudades da sua casa, então você decide voltar para o Brasil o mais rápido possível, você sabe que existem voos entre algumas cidades da europa e que cada voo tem um tempo de duração, você quer saber qual o menor tempo que você pode levar para chegar no Brasil.
É possível modelar esse problema como um grafo, onde:
Vértices: Cada uma das cidades disponíveis que possuem voos.
Arestas: Cada um dos voos. Aqui, o peso de cada aresta é o tempo de duração de voo.
📝 Implementação
Vamos ver como implmentar o algoritmo de Dijkstra para resolver o problema.
É necessário pensar na lógica das duas partes principais do algoritmo: como encontrar o vértice mais próximo (vamos chamar de u) e como atualizar os valores para os vizinhos de u.
Podemos manter todas as distâncias em uma fila de prioridade (priority queue, heap), dessa maneira esse passo custa O(log N).
Para o segundo passo, simplesmente percorremos por todos os vizinhos do vértice u e atualizamos as distâncias se necessário.
Vamos supor neste problema que o número de cidades é N ≤ 10.000 e que uma viagem não passa de 1000 minutos.
O código, então, fica assim:
import heapq
# número de vértices e arestas
n, m = map(int, input().split())
# vértice de origem
cidade_origem, cidade_destino = map(int, input().split())
# vetor de distâncias
distancia = [float('inf')] * (n + 1)
# vetor para saber quando um vértice já foi processado
processado = [False] * (n + 1)
# lista de adjacência, com o peso
vizinhos = [[] for _ in range(n + 1)]
def Dijkstra(S):
# iniciamos a distância do vértice origem como 0 e começaamos por ele
distancia[S] = 0
fila = [(0, S)]
while fila:
davez = -1
while fila:
# pegamos a aresta com menor peso
dist, atual = heapq.heappop(fila)
# verificamos se ela já foi processada
if not processado[atual]:
davez = atual
break
# se todas as arestas já foram processadas, então terminamos
if davez == -1:
break
# marcamos que o vértice davez foi processado
processado[davez] = True
# agora, tentamos atualizar a distância dos vizinhos de davez
for dist, atual in vizinhos[davez]:
# a nova possível distância é distancia[davez] + dist
if distancia[atual] > distancia[davez] + dist:
# atualizamos a distância se ela ficou menor
distancia[atual] = distancia[davez] + dist
heapq.heappush(fila, (distancia[atual], atual))
for _ in range(m):
x, y, tempo = map(int, input().split())
vizinhos[x].append((tempo, y))
vizinhos[y].append((tempo, x))
Dijkstra(cidade_origem)
print(distancia[cidade_destino])A complexidade do algoritmo é O(M * log N), onde M é o número de arestas e N é o número de vértices.
Podemos ver, então que o algoritmo de Dijkstra é uma ótima escolha para resolver problemas de menor caminho em grafos com arestas de peso não negativo.
Last updated