¿Por qué no podemos encontrar los caminos más cortos con pesos negativos simplemente agregando una constante para que todos los pesos sean positivos?

Actualmente estoy leyendo la introducción a los algoritmos y encontré el algoritmo de Johnson que depende de asegurarse de que todas las rutas sean positivas.

el algo depende de encontrar una nueva función de peso (w ') que sea positiva para todos los bordes y mantenga la corrección de las relaciones de rutas más cortas.

Lo hace calculando los valores h (s), h (d) que se agregarán al valor original w.

Mi pregunta es, ¿por qué no encontrar la w más pequeña en el gráfico y agregarla a todos los bordes? Esto satisfará ambas condiciones y requerirá menos cálculo.

algorithms graph-theory graphs shortest-path Mr.Me
fuente

¿Has intentado probar tu reclamo o encontrar un contraejemplo? Pista: tu intuición está equivocada. (Comunidad, estoy bastante seguro de que esto es un duplicado. ¿Puedes encontrarlo?)

Raphael

@Raphael Estoy bastante seguro de que también es un engañado, pero pensé que sería más rápido responderlo que encontrarlo.

David Richerby

@Raphael Lo siento, ya que no pude formular mi pregunta en un formato específico, no pude buscarla.

Mr.Me

Tenemos una pregunta que ya explica esto , pero se marcó como un duplicado de otra pregunta que es bastante confusa y difícil de entender, y que combina múltiples preguntas diferentes . Por lo tanto, creo que esta pregunta tiene valor sobre lo que teníamos antes. Si lo desea, supongo que podríamos reorientar los duplicados (ciérrelos como duplicado de esto en lugar de lo que apuntan actualmente).

Respuestas:

Agregar un peso a cada borde agrega más peso a las rutas largas que a las cortas. (Largo en el sentido de tener muchas aristas).

$-2$ $a$ $b$ $3$ $1$ $2$ $5$ $6$

David Richerby
fuente

El aumento de cada peso de borde en la misma cantidad no necesariamente aumenta cada ruta en la misma cantidad de distancia. Por el contrario, el aumento de las rutas a menudo son desproporcionadas, lo que depende de cuántos bordes tiene la ruta.

Pendechosen
fuente

Este efecto ya se menciona en la otra respuesta.

Yuval Filmus

Lo reformulé hasta el punto de confusión.

Pendechosen