0
205
ViewsSedgewick/Wayne "BellmanFordSP.java": ¿cómo "findNegativeCycle" se asegura de que se devuelva un ciclo negativo?
En la implementación de Sedgewick y Wayne del algoritmo Bellman-Ford ( https://algs4.cs.princeton.edu/44sp/BellmanFordSP.java ), el método findNegativeCycle usa EdgeWeightedDirectedCycle ( https://algs4.cs.princeton.edu/44sp /EdgeWeightedDirectedCycle.java ) para encontrar un ciclo dirigido en el árbol de la ruta más corta (los bordes en la matriz edgeTo ).
Asimismo, en el método de check se afirma que el peso de este ciclo dirigido es negativo. Por lo tanto, si las aserciones de Java están habilitadas, el constructor BellmanFordSP lanzará una excepción si el método de ciclo negativeCycle devuelve un ciclo cuyo peso no es negativo.
Pregunta: si el árbol de la ruta más corta contiene un ciclo de ponderación cero y un ciclo de ponderación negativa, ¿qué garantiza que EdgeWeightedDirectedCycle no devuelva el ciclo de ponderación cero (provocando así un error de aserción)?
1 answers
Answer question0
La implementación enlazada de Bellman-Ford no garantiza que el ciclo de ponderación negativa se devuelva en presencia de un ciclo de ponderación negativa y de ponderación cero.
El siguiente gráfico hará que BellmanFordSP.java se bloquee (con un AssertionError ) cuando el vértice de inicio sea 2 , porque el peso del ciclo encontrado es igual a cero (comando java -ea BellmanFordSP.java <graph.txt> 2 ):
8 9 0 1 3.0 1 2 -3.430337482745286 2 3 0 3 4 -2 4 5 -5 5 0 0 3 6 -4 6 7 -5 7 3 9 Aquí está el gráfico anterior visualizado: 
En última instancia, el error se debe a un error de redondeo de punto flotante.
Cuando el vértice 3 se relaja por segunda vez, la distancia actual a este vértice es igual a -7.430337482745286 . El borde 3→6 (de peso -4.0 ) hará que la distancia a 6 se actualice a -7.430337482745286 + -4.0 , que (cuando se usan números de punto flotante de precisión doble) es igual a -11.430337482745287 (observe que el dígito final es 7 y no 6). Cuando se relaja 6 , la distancia a 7 se actualiza a -16.430337482745287 ( -11.430337482745287 + -5.0 ) lo que, finalmente, hace que la relajación del vértice 7 actualice la distancia a 3 a -7.430337482745287 ( -16.430337482745287 + 9.0 ). Esta nueva distancia a 3 es menor que la distancia anterior de -7.430337482745286 (debido al error de redondeo de punto flotante), lo que significa que el borde 7→3 reemplaza al borde 2→3 en el árbol de la ruta más corta. Esto da como resultado que el árbol de la ruta más corta ya no contenga el ciclo negativo (porque ya no contiene 2→3), sino el ciclo de peso cero.