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ń.
2
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ą).
—
DW