El algoritmo más rápido de ruta más corta (SPFA) es una mejora del algoritmo de Bellman-Ford que calcula las rutas más cortas de una sola fuente en un gráfico dirigido ponderado. Se cree que el algoritmo funciona bien en gráficos dispersos aleatorios y es particularmente adecuado para gráficos que contienen bordes de peso negativo. [1] Sin embargo, la complejidad del peor caso de SPFA es la misma que la de Bellman-Ford, por lo que para gráficos con pesos de borde no negativos se prefiere el algoritmo de Dijkstra . El algoritmo SPFA fue publicado por primera vez por Edward F. Moore en 1959, como una generalización de la primera búsqueda de amplitud ; [2]SPFA es el "algoritmo D" de Moore El nombre, "Algoritmo más rápido de ruta más corta (SPFA)", fue dado por FanDing Duan, un investigador chino que redescubrió el algoritmo en 1994. [3]
Algoritmo
Dado un gráfico dirigido ponderado y un vértice fuente , el algoritmo SPFA encuentra la ruta más corta desde , a cada vértice , en el gráfico. La longitud del camino más corto desde a se almacena en para cada vértice .
La idea básica de SPFA es la misma que la del algoritmo de Bellman-Ford en que cada vértice se usa como candidato para relajar sus vértices adyacentes. La mejora con respecto a este último es que en lugar de probar todos los vértices a ciegas, SPFA mantiene una cola de vértices candidatos y agrega un vértice a la cola solo si ese vértice está relajado. Este proceso se repite hasta que no se pueden relajar más vértices.
A continuación se muestra el pseudocódigo del algoritmo. [4] Aquí es una cola de primeros en entrar, primero en salir de vértices candidatos, y es el peso del borde de .
procedimiento Algoritmo de ruta más corta ( G , s ) 1 para cada vértice v ≠ s en V ( G ) 2 d ( v ): = ∞ 3 d ( s ): = 0 4 presione s en Q 5 mientras Q no esté vacío haga 6 u : = encuesta Q 7 para cada borde ( u , v ) en E ( G ) haga 8 si d ( u ) + w ( u , v )v ) luego 9 d ( v ): = d ( u ) + w ( u , v ) 10 si v no está en Q, entonces 11 empuje v en Q
El algoritmo también se puede aplicar a un gráfico no dirigido reemplazando cada borde no dirigido con dos bordes dirigidos de direcciones opuestas.
Prueba de corrección
Demostraremos que el algoritmo nunca calcula longitudes de ruta más cortas incorrectas.
- Lema : Siempre que se comprueba que la cola está vacía, cualquier vértice que actualmente pueda causar relajación está en la cola.
- Prueba : Queremos demostrar que si para dos vértices cualesquiera y en el momento en que se comprueba la condición, está en la cola. Lo hacemos por inducción sobre el número de iteraciones del bucle que ya han ocurrido. Primero notamos que esto ciertamente se mantiene antes de que se ingrese al ciclo: si , entonces la relajación no es posible; la relajación es posible desde , y esto se agrega a la cola inmediatamente antes de ingresar al ciclo while. Ahora, considere lo que sucede dentro del ciclo. Un vértice se abre, y se usa para relajar a todos sus vecinos, si es posible. Por lo tanto, inmediatamente después de esa iteración del ciclo, no es capaz de causar más relajaciones (y ya no tiene que estar en la cola). Sin embargo, la relajación de puede hacer que otros vértices sean capaces de causar relajación. Si existe alguna tal que antes de la iteración del ciclo actual, entonces ya está en la cola. Si esta condición se cumple durante la iteración del ciclo actual, entonces aumentado, lo cual es imposible, o disminuido, lo que implica que estaba relajado. Pero después está relajado, se agrega a la cola si aún no está presente.
- Corolario : El algoritmo termina cuando y solo cuando no son posibles más relajaciones.
- Prueba : si no son posibles más relajaciones, el algoritmo continúa eliminando vértices de la cola, pero no agrega más a la cola, porque los vértices se agregan solo después de relajaciones exitosas. Por lo tanto, la cola se vacía y el algoritmo termina. Si son posibles más relajaciones, la cola no está vacía y el algoritmo continúa ejecutándose.
El algoritmo no termina si los ciclos de peso negativo son accesibles desde la fuente. Vea aquí una prueba de que las relajaciones siempre son posibles cuando existen ciclos de peso negativo. En un gráfico sin ciclos de peso negativo, cuando no son posibles más relajaciones, se han calculado las trayectorias más cortas correctas ( prueba ). Por lo tanto, en gráficos que no contienen ciclos de peso negativo, el algoritmo nunca terminará con longitudes de ruta más cortas incorrectas. [5]
Tiempo de ejecución
El peor tiempo de ejecución del algoritmo es , al igual que el algoritmo estándar de Bellman-Ford . [1] Los experimentos sugieren que el tiempo de ejecución promedio es, y de hecho esto es cierto en gráficos aleatorios, pero es posible construir gráficos dispersos donde SPFA se ejecuta en el tiempo como el algoritmo habitual de Bellman-Ford. [6]
Técnicas de optimización
El rendimiento del algoritmo está fuertemente determinado por el orden en que se utilizan los vértices candidatos para relajar otros vértices. De hecho, sies una cola de prioridad, entonces el algoritmo se parece mucho al de Dijkstra. Sin embargo, dado que aquí no se utiliza una cola de prioridad, a veces se emplean dos técnicas para mejorar la calidad de la cola, lo que a su vez mejora el rendimiento del caso medio (pero no el rendimiento del peor de los casos). Ambas técnicas reorganizan el orden de los elementos enpara que los vértices más cercanos a la fuente se procesen primero. Por lo tanto, al implementar estas técnicas, ya no es una cola de primero en entrar, primero en salir, sino más bien una lista doble enlazada normal o una cola de dos extremos.
Técnica de etiqueta pequeña primero ( SLF ). En la línea 11, en lugar de presionar siempre el vértice hasta el final de la cola, comparamos a e inserte al frente de la cola si es más pequeño. El pseudocódigo para esta técnica es (después de presionar hasta el final de la cola en la línea 11):
procedimiento Small-Label-First ( G , Q ) si d (back ( Q ))Q )) luego u: = retroceder de Q empujar u al frente de Q
Técnica Large Label Last ( LLL ). Después de la línea 11, actualizamos la cola para que el primer elemento sea más pequeño que el promedio y cualquier elemento más grande que el promedio se mueva al final de la cola. El pseudocódigo es:
procedimiento Large-Label-Last ( G , Q ) x : = promedio de d ( v ) para todo v en Q mientras que d (front ( Q ))> x u : = pop front of Q empuje u hacia atrás de Q
Referencias
- ^ a b Acerca del llamado algoritmo SPFA
- ^ Moore, Edward F. (1959). "El camino más corto a través de un laberinto". Actas del Simposio internacional sobre la teoría de la conmutación . Prensa de la Universidad de Harvard. págs. 285-292.
- ^ Duan, Fanding (1994), "关于 最短 路径 的 SPFA 快速 算法 [Acerca del algoritmo SPFA]" , Journal of Southwest Jiaotong University , 29 (2): 207–212
- ^ http://codeforces.com/blog/entry/16221
- ^ "Algoritmo más rápido de la ruta más corta" . wcipeg .
- ^ Ke, Yang. "Peor caso de prueba para SPFA" .