Dlaczego nie możemy znaleźć najkrótszych ścieżek o ujemnych wagach, po prostu dodając stałą, aby wszystkie wagi były dodatnie?

Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne.

algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych ścieżek.

Odbywa się to poprzez obliczenie wartości h (s), h (d), które należy dodać do pierwotnej wartości w.

Moje pytanie brzmi: dlaczego nie znaleźć najmniejszego w na wykresie i dodać go do wszystkich krawędzi? spełni to oba warunki i będzie wymagało mniej obliczeń.

algorithms graph-theory graphs shortest-path Mr.Me
źródło

Czy próbowałeś udowodnić swoje roszczenie lub znaleźć przeciwny przykład? Wskazówka: Twoja intuicja jest błędna. (Społeczność, jestem prawie pewien, że to duplikat. Czy możesz go znaleźć?)

Raphael

@Raphael Jestem prawie pewien, że to też dupe, ale pomyślałem, że szybciej byłoby odpowiedzieć na to pytanie niż znaleźć dupe.

David Richerby,

@Raphael Przykro mi, ponieważ nie mogłem sformułować pytania w określonym formacie, nie mogłem go wyszukać.

Mr.Me

Mamy pytanie, które już to wyjaśnia , ale zostało oznaczone jako duplikat innego pytania, które jest dość mylące i trudne do zrozumienia, i które łączy w sobie wiele różnych pytań . Dlatego myślę, że to pytanie ma wartość nad tym, co mieliśmy wcześniej. Jeśli chcesz, przypuszczam, że moglibyśmy ponownie skierować duplikatów (zamknij je jako duplikat zamiast tego, co obecnie wskazują).

Odpowiedzi:

Dodanie ciężaru do każdej krawędzi zwiększa ciężar długich ścieżek niż ścieżek krótkich. (Długi w znaczeniu posiadania wielu krawędzi.)

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

David Richerby
źródło

Zwiększenie ciężaru każdej krawędzi o tę samą kwotę niekoniecznie zwiększa każdą ścieżkę o tę samą odległość. Wzrost ścieżek jest często nieproporcjonalny, co zależy od tego, ile krawędzi ma ścieżka.

Pendechosen
źródło

Ten efekt jest już wspomniany w innej odpowiedzi.

Yuval Filmus,

Właśnie sformułowałem to do pomieszania.

Pendechosen