¿Por qué la mayoría de los algoritmos de gráficos no se adaptan tan fácilmente a los números negativos?

Question

El Algorithm Design Manual dice:

La mayoría de los algoritmos de grafos no se adaptan tan fácilmente a los números negativos. De hecho, los algoritmos de ruta más cortos tienen problemas con los números negativos, y ciertamente no generan la ruta más larga posible usando esta técnica.

¿Pero por qué? Cuando simplemente agregamos un - negativo frente al peso original, creo que la mayoría de los problemas de gráficos que involucran el peso se pueden repartir por igual, ¿verdad?

Answer 1

Porque cuando considera el costo mínimo o máximo de una ruta siempre termina considerando la suma de todos los pasos individuales.

Y dado que muchos de estos algoritmos funcionan localmente eligiendo el mejor enfoque paso a paso (con un paso de diferente magnitud, por supuesto), tener pesos negativos solo generaría ciclos o falsos positivos.

Tener un peso negativo implica que el costo de una ruta puede disminuir en el futuro, es por eso que crea problemas: no se pudieron excluir rutas de una lista de buenas rutas posibles incluso después de llegar a un punto en el que ahora es más caro que el otro porque puedes encontrar bordes con peso negativo que cambian la situación.

Sólo como ejemplo: si tiene dos nodos conectados mutuamente por dos bordes de peso 1 y -2 se podría crear un ciclo entre ellos para determinar un camino con arbitraria bajo costo (incluso -∞).

Answer 2

De hecho, más cortos algoritmos del camino tienen problemas con números negativos,

Esto es cierto para Dijkstra's Algorithm, pero no para los algoritmos del camino más corto en general. El Bellman-Ford Algorithm puede manejar pesos de borde negativo, siempre que el gráfico no contenga ciclos negativos. Sin embargo:

Bellman-Ford puede detectar ciclos negativos e informar de su existencia, pero no puede producir una respuesta correcta si un ciclo negativo no es accesible desde la fuente.

Answer 3

Voy a agregar una respuesta específica para el problema de ruta más corta. El problema general con bordes negativos se describe bien en Jack’s answer.

Considere un gráfico G = (V, E) con bordes de longitud l(e) ≤ 0 para cada borde e ∈ E. La ruta más corta en G es la misma que la ruta más larga en G' con l'(e) = - l(e) ≥ 0 ∀e ∈ E. Se sabe que Longest path problem es NP-hard en gráficos generales. Aunque se puede resolver en tiempo lineal en DAG y otras clases de gráficos.

Como cls answered, el problema está en los ciclos negativos solamente y Bellman-Ford algorithm puede hacer frente a algunos bordes que son negativos. Pero el algoritmo de ruta más larga debe hacer frente a los ciclos en el gráfico y Bellman-Ford no puede dar una respuesta correcta en los gráficos con ciclos negativos. Por lo tanto, el algoritmo Bellman-Ford se puede usar para calcular la ruta más larga solo en gráficos sin ciclos positivos. Mencionando, porque esa idea es obviously not uncommon.