Ujemny cykl

Powrót do listy wątków

Jeśli w ważonym grafie skierowanym istnieje ujemny cykl, to wcale nie musi oznaczać,
że między jakąś parą wierzchołków nie istnieje najkrótsza ścieżka ?

Jeśli tak, to jeżeli w algorytmie Johnsona stwierdzimy istnienie ujemnego cyklu w oryginalnym grafie, to przerywamy całą pracę, mimo że dla niektórych par wierzchołków można najkrótszą ścieżkę wyznaczyć. Jak wtedy "przerobić" algorytm Johnsona, by mimo wszystko znajdował wyniki tam, gdzie to możliwe ? Paweł Maśluch, 2016-03-13 20:24:09
Jedną z częścią składowych algorytmu Johnsona jest algorytm Dijkstry.
Działanie algorytmu opiera się na podstawowym założeniu: w momencie, gdy z kolejki priorytetowej zdejmowany jest wierzchołek o oszacowaniu wagi ścieżki ze źródła równej d - to właściwa waga ścieżki do tego wierzchołka wynosi po prostu d (bo 1) wszystkie ścieżki o wadze mniejszej niż d zostały już rozważone oraz 2) wagi krawędzi są nieujemne).
W algorytmie Johnsona najpierw uruchamiany jest algorytm Bellmana-Forda, aby zmodyfikować funkcję wagi krawędzi, tak aby w algorytmie Dijkstry rzeczywiście wagi krawędzi były nieujemne.
Jeśli w grafie istnieje cykl... czy na pewno możliwe jest naprawienie funkcji wagowej, aby wszystkie wagi były nieujemne? Karol Pokorski, 2016-03-16 11:42:07