Pourquoi ne pouvons-nous pas trouver les chemins les plus courts avec des poids négatifs en ajoutant simplement une constante pour que tous les poids soient positifs?

Je lis actuellement l'introduction aux algorithmes et je suis venu de l'algorithme de Johnson qui dépend de s'assurer que tous les chemins sont positifs.

l'algo dépend de la recherche d'une nouvelle fonction de poids (w ') positive pour toutes les arêtes et conservant l'exactitude des relations de chemins les plus courts.

Il le fait en calculant les valeurs h (s), h (d) à ajouter à la valeur d'origine w.

Ma question est, pourquoi ne pas simplement trouver le plus petit w dans le graphique et l'ajouter à tous les bords? cela satisfera les deux conditions et nécessitera moins de calcul.

algorithms graph-theory graphs shortest-path Mr.Me
la source

Avez-vous essayé de prouver votre affirmation ou de trouver un contre-exemple? Astuce: votre intuition est fausse. (Communauté, je suis presque sûr qu'il s'agit d'un doublon. Pouvez-vous le trouver?)

Raphael

@Raphael Je suis presque sûr que c'est dupe aussi, mais je me suis dit qu'il serait plus rapide de répondre que de trouver le dupe.

David Richerby

@Raphael Je suis désolé car je n'ai pas pu formuler ma question dans un format spécifique, je ne pouvais pas la rechercher.

Mr.Me

Nous avons une question qui explique déjà cela , mais elle a été marquée comme un dup d' une autre question qui est assez déroutante et difficile à comprendre, et qui mélange plusieurs questions différentes . Par conséquent, je pense que cette question a de la valeur par rapport à ce que nous avions auparavant. Si vous le vouliez, je suppose que nous pourrions recibler les doublons (fermez-les en tant que dupes de ceci au lieu de ce qu'ils pointent actuellement).

Réponses:

L'ajout d'un poids à chaque bord ajoute plus de poids aux chemins longs qu'aux chemins courts. (Long dans le sens d'avoir de nombreux bords.)

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

David Richerby
la source

L'augmentation de chaque poids de bord de la même quantité n'augmente pas nécessairement chaque chemin de la même distance. Au contraire, l'augmentation des chemins est souvent disproportionnée, ce qui dépend du nombre d'arêtes du chemin.

Pendechosen
la source

Cet effet est déjà mentionné dans l'autre réponse.

Yuval Filmus

Je viens de la reformuler au point de la confusion.

Pendechosen