Publicado · en mejora
Algorithm
Calcula caminos mínimos con Dijkstra, Bellman-Ford y Floyd-Warshall, y construye árboles generadores mínimos con Kruskal y Prim.
El problema del camino mínimo busca, en un grafo ponderado, el camino de menor peso total entre dos vértices. Un árbol generador mínimo (MST) es el conjunto de aristas más barato que conecta todos los vértices de un grafo no dirigido sin formar ciclos. Los algoritmos centrales de este tema son Dijkstra, Bellman-Ford, Floyd-Warshall, BFS 0-1, Kruskal y Prim.
Estos algoritmos funcionan dentro de los navegadores de mapas, de protocolos de enrutamiento como OSPF y RIP, de la búsqueda de rutas en videojuegos, del diseño de redes de cables y tuberías y del agrupamiento de datos. También son habituales en entrevistas técnicas, porque muestran si sabes modelar un problema como grafo y elegir el algoritmo adecuado según los pesos: negativos o no, solo 0 y 1, grafo disperso o denso.
Conviene dominar primero BFS y las colas de prioridad (montículos). Después, aprende la relajación, la operación que comparten todos los algoritmos de caminos mínimos, y sigue Dijkstra a mano en un grafo pequeño. A continuación, entiende por qué las aristas negativas exigen Bellman-Ford, implementa Kruskal con union-find y termina con ejercicios que ejecutan Dijkstra sobre un grafo de estados ampliado.
Todos los algoritmos de caminos mínimos se basan en la relajación: comprobar si pasar por u da un camino más corto hasta v. Solo cambia el orden en que relajan las aristas.
Con pesos no negativos, un montículo binario extrae y fija cada vez el vértice más cercano, y obtiene todas las distancias desde un origen en O((V + E) log V).
Bellman-Ford admite aristas negativas y detecta ciclos negativos; Floyd-Warshall calcula la distancia entre todos los pares de vértices en O(V^3).
Kruskal añade aristas de la más ligera a la más pesada y evita ciclos con union-find; Prim hace crecer un único árbol por su arista saliente más barata. La propiedad del corte garantiza que ambos son correctos.
heapq extrae pares (distancia, vértice) en orden de distancia; si la distancia extraída es mayor que la registrada, el par está obsoleto y se omite. Cuando mejora la distancia de un vecino, se actualiza y se inserta un par nuevo. Al ejecutar python dijkstra.py se imprimen las distancias mínimas desde 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 te llevan desde la instalación hasta las ideas clave de Camino mínimo y árbol generador mínimo.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Camino mínimo y árbol generador mínimo.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.