¿Por qué no podemos ejecutar Bellman Ford desde la fuente y relajar los bordes de los vecinos de forma recursiva y hacer una sola pasada a través de los bordes?

+1 a la respuesta de Eugene Yarovo.

Personalmente, creo que Bellman Ford no es más que una optimización de borde de relajación para un Djikstra (seguro, dirás que estamos buscando caminos, no un vértice terminal, pero eso es lo que hace la relajación). Es la misma fórmula de actualización a distancia. La relajación NECESITA, en el peor de los casos, un orden de | E || V | se relaja, porque una pasada a través del gráfico solo puede minimizar la distancia desde una fuente a algún nodo terminal ‘t’ para algunas rutas [math] P = \ {p_ {1}, .., p_ {n} \} [/ math] , con longitudes de peores casos [matemáticas] | V | – 1 [/ math] (Debe asegurarse de que cada vértice en alguna ruta [math] p = (v_ {1}… v_ {m}) [/ math] es [math] d_ {min} (s, v) [/mates]). Por lo tanto, puede mostrar claramente, utilizando trucos de Límite inferior, que [matemática] O (| V || E |) [/ matemática] es la mejor optimización de casos, porque necesita verificar la distancia más corta actual asegurándose de que la distancia a CADA nodo en el camino es el más corto. Entonces, esta es la razón por la que tenemos un bucle externo de [matemáticas] \ {1, | V | – 1 \} [/ matemáticas]. Aquí es donde entra la relajación. Por definición, al comenzar desde la fuente, has inclinado tu árbol de recursión. No hay optimización asintótica posible.

Con respecto a sus pensamientos, como se ha dicho, es una posible optimización, pero la necesidad de controles en el vecindario casi seguramente garantiza la necesidad de visitar nuevamente un vértice previamente visitado al menos una vez para un vértice aleatorio en el vecino, a través de un Conjunto de intersección barrios Entonces, seguro que podría optimizar para algunos vecindarios, y algunos análisis aleatorios pueden dar un límite más estricto para una estructura especial de gráficos (DAG en su mayoría, me dice mi instinto). Pero, como se ha dicho, no hay forma de que la complejidad asintótica en el peor de los casos esté disminuyendo.

Puede encontrar útil esta pregunta: ¿Qué hace el procedimiento de relajación en el algoritmo de Bellman-Ford?

Esto es válido y se conoce como Yen primera mejora de Bellman Ford.