Algoritmo BMSSP2025

Complejidad: O(m log^2/3 n) - ¡Rompe la barrera del sorting!

Grafo:

Paso 1 / 0

Velocidad:

500ms

Pseudocódigo BMSSP

1function BMSSP(level, bound B, frontier S):

2 if level = 0:

3 return BaseCase(B, S) // Mini-Dijkstra

5 P, W ← FindPivots(B, S) // Reduce frontier

6 D ← initialize with pivots P

7 U ← ∅

9 while D not empty and |U| < threshold:

10 S_i, B_i ← Pull smallest from D

11 B'_i, U_i ← BMSSP(level-1, B_i, S_i)

12 U ← U ∪ U_i

14 for each edge (u,v), u ∈ U_i:

15 relax edge and update D

17 return B', U

19function FindPivots(B, S):

20 W ← S

21 for i ← 1 to k: // k relaxation steps

22 relax all edges from W_{i-1}

23 W_i ← newly reached vertices

24 W ← W ∪ W_i

26 // Pivots = roots of large subtrees (≥k vertices)

27 P ← {u ∈ S : subtree(u) ≥ k}

28 return P, W

Ejecuta el algoritmo para ver el estado

Leyenda de Colores

No visitado

En frontier

Pivot

Procesando

Completado

1El problema con Dijkstra

Dijkstra mantiene un "frontier" que puede tener Θ(n) vértices. Ordenar constantemente estos vértices lleva a Ω(n log n) operaciones.

2FindPivots - Reducción del Frontier

Ejecutamos k pasos de relajación (estilo Bellman-Ford). Los "pivots" son raíces de subárboles con ≥k vértices. Solo hay |U|/k pivots.

3Divide and Conquer

En vez de ordenar todo el frontier, particionamos recursivamente. Cada nivel reduce el problema en factor 2^t.

4La ganancia

El trabajo por vértice se reduce de log(n) a log(n)/log^Ω(1)(n), rompiendo la barrera del sorting.

Comparación con Dijkstra

Dijkstra

Complejidad:O(m + n log n)

Operaciones heap:n extracciones, m decrease-keys

Bottleneck:Ordenamiento implícito de n vértices

BMSSP (Nuevo)

Complejidad:O(m log^(2/3) n)

Reducción pivot:Solo |U|/k pivots por nivel

Niveles:O(log n / t) niveles de recursión

¿Cómo rompe la barrera?

En vez de mantener un orden total de todos los n vértices (que requiere Ω(n log n)), el algoritmo BMSSP solo ordena los pivots - aproximadamente |U|/k vértices por nivel. Al reducir el número de vértices que necesitan ser ordenados en cada nivel por un factor de k = log^1/3(n), el trabajo total se reduce a O(m log^2/3 n).