Lançado · em melhoria
Algorithm
Calcule caminhos mínimos com Dijkstra, Bellman-Ford e Floyd-Warshall e construa árvores geradoras mínimas com Kruskal e Prim.
O problema do caminho mínimo procura, em um grafo ponderado, o caminho de menor peso total entre dois vértices. Uma árvore geradora mínima (MST) é o conjunto de arestas mais barato que liga todos os vértices de um grafo não direcionado sem formar ciclos. Os algoritmos centrais deste tema são Dijkstra, Bellman-Ford, Floyd-Warshall, BFS 0-1, Kruskal e Prim.
Esses algoritmos rodam em aplicativos de navegação, em protocolos de roteamento como OSPF e RIP, na busca de caminhos em jogos, no projeto de redes de cabos e tubulações e em clusterização. Também aparecem muito em entrevistas técnicas, porque mostram se você sabe modelar um problema como grafo e escolher o algoritmo certo para os pesos: negativos ou não, apenas 0 e 1, grafo esparso ou denso.
Comece dominando BFS e filas de prioridade (heaps). Depois aprenda o relaxamento, a operação comum a todos os algoritmos de caminho mínimo, e acompanhe o Dijkstra à mão em um grafo pequeno. Em seguida, entenda por que arestas negativas exigem Bellman-Ford, implemente Kruskal com union-find e termine com exercícios que rodam Dijkstra sobre um grafo de estados ampliado.
Todos os algoritmos de caminho mínimo se apoiam no relaxamento: verificar se passar por u gera um caminho mais curto até v. Eles diferem apenas na ordem em que relaxam as arestas.
Com pesos não negativos, um heap binário retira e fixa a cada passo o vértice mais próximo, obtendo todas as distâncias a partir de uma origem em O((V + E) log V).
Bellman-Ford aceita arestas negativas e detecta ciclos negativos; Floyd-Warshall calcula a distância entre todos os pares de vértices em O(V^3).
Kruskal adiciona arestas da mais leve para a mais pesada e evita ciclos com union-find; Prim faz crescer uma única árvore pela aresta de saída mais barata. A propriedade do corte garante que ambos estão corretos.
heapq retira pares (distância, vértice) em ordem de distância; um par cuja distância é maior que a registrada está desatualizado e é ignorado. Quando a distância de um vizinho melhora, o código a atualiza e insere um novo par. Ao executar python dijkstra.py, são impressas as distâncias mínimas a partir de A: {'A': 0, 'B': 3, 'C': 1, 'D': 4}.
dijkstra.py
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A")) # {'A': 0, 'B': 3, 'C': 1, 'D': 4}
python dijkstra.pySeis capítulos que levam você da instalação aos conceitos essenciais de Caminho mínimo e árvore geradora mínima.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Caminho mínimo e árvore geradora mínima.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.