Visualización de Algoritmos de Camino Más Corto
Explora de forma interactiva cómo funcionan Dijkstra y el nuevo algoritmo que rompe la barrera del sorting en grafos dirigidos.
Algoritmo de Dijkstra
El algoritmo clásico propuesto por Edsger Dijkstra en 1959. Encuentra el camino más corto desde un vértice fuente a todos los demás vértices en un grafo con pesos no negativos.
Complejidad
O(m + n log n)
Con Fibonacci Heap o Relaxed Heap
Características:
- Usa una cola de prioridad (heap)
- Procesa vértices en orden de distancia
- Produce un ordenamiento implícito de vértices
- Considerado óptimo por décadas
Nuevo Algoritmo BMSSP2025
El primer algoritmo determinístico que rompe la barrera del sorting en grafos dirigidos. Presentado por Duan, Mao, Mao, Shu & Yin.
Complejidad
O(m log2/3 n)
¡Mejor que Dijkstra en grafos sparse!
Ideas Clave:
- FindPivots: Reduce el frontier
- BMSSP: Divide and conquer recursivo
- Combina Dijkstra + Bellman-Ford
- Evita ordenar todos los vértices
¿Por qué es importante?
Rompe una Barrera
Por ~70 años se creía que O(n log n) era el límite inferior para SSSP. Este algoritmo demuestra lo contrario.
Mejor en Sparse
En grafos con m = O(n), la mejora es significativa: de O(n log n) a O(n log2/3 n).
Determinístico
A diferencia de resultados anteriores, este algoritmo es completamente determinístico (sin randomización).
Referencia del Paper
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin. "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths". arXiv:2504.17033v2 [cs.DS], July 2025.
Instituciones: Tsinghua University, Stanford University, Max Planck Institute for Informatics.