Algoritmo de Bellman-Ford: ¿por qué los bordes se pueden actualizar fuera de servicio?

El algoritmo Bellman-Ford determina la ruta más corta desde una fuente a todos los demás vértices. Inicialmente, la distancia entre todos los demás vértices se establece en . Luego se calcula la ruta más corta desde hasta cada vértice; esto continúa para las iteraciones . Mis preguntas son:$s$$s$$\infty$$s$$|V|-1$

• ¿Por qué debe haber iteraciones ?$|V|-1$
• ¿Importaría si revisara los bordes en un orden diferente?
  Digamos, si primero verifico los bordes 1,2,3, pero luego en la segunda iteración verifico 2,3,1.

El profesor Eric del MIT dijo que el orden no importaba, pero esto me confunde: ¿el algoritmo no actualizaría incorrectamente un nodo basado en el borde si su valor dependiera del borde pero se actualiza después de ?$x_2$$x_1$$x_1$$x_2$

Considere el camino más corto de a t , s , v 1 , v 2 , ... , v k , t . Este camino consta de como máximo | V | - 1 bordes, porque repetir un vértice en un camino más corto siempre es una mala idea (o al menos hay un camino más corto que no repite vértices), si no tenemos ciclos de peso negativos.$s$$t$$s, v_1, v_2, \dots, v_k, t$$|V|-1$

En la primera ronda, sabemos que el borde se relajará, por lo que la estimación de distancia para v 1 será correcta después de esta ronda. Tenga en cuenta que no tenemos idea de qué v 1 es en este momento, pero como hemos relajado todos los bordes, también debemos haber relajado este. En la segunda ronda, nos relajamos ( v 1 , v 2 ) en algún momento. Todavía no tenemos idea de qué son v 1 o v 2 , pero sabemos que sus estimaciones de distancia son correctas.$(s, v_1)$$v_1$$v_1$$(v_1, v_2)$$v_1$$v_2$

Repitiendo esto, después de una ronda , nos hemos relajado ( v k , t ) , después de lo cual la distancia estimada para t es correcta. No tenemos idea de qué es k hasta que todo el algoritmo haya terminado, pero sabemos que sucederá en algún momento (suponiendo que no haya ciclos de peso negativos).$k+1$$(v_k, t)$$t$$k$

Entonces, la observación crucial es que después de la ronda , el i -ésimo nodo del camino más corto debe tener su estimación de distancia establecida en el valor correcto. Como el camino es a lo sumo | V | - 1 bordes largos, | V | - 1 ronda es suficiente para encontrar este camino más corto. Si un | V | La ronda todavía cambia algo, entonces algo extraño está sucediendo: todos los caminos ya deberían estar 'establecidos' a sus valores finales, por lo que debemos tener la situación de que existe algún ciclo de peso negativo.$i$$i$$|V|-1$$|V|-1$$|V|$

Lo más largo que puede ser un camino sin ningún ciclo es |V|. Comenzamos con una fuente, por lo que ya tenemos una ruta de longitud 1, por lo que necesitamos |V| - 1más nodos para obtener la ruta más larga.

El orden no importa porque cada orden mantendrá la invariante: después de las niteraciones, el valor para cada nodo es menor o igual al costo de la ruta de costo mínimo desde sel nodo que contiene la mayoría de los nbordes.

Si, al comienzo de una iteración, el costo es correcto hasta los nnodos, entonces al final de la iteración es correcto hasta los n+1nodos. Un reordenamiento puede hacer que algunos nodos tengan un costo menor antes de que normalmente se actualicen, pero eventualmente se actualizarán de todos modos.