Czy mam rację co do różnic między algorytmami Floyda-Warshalla, Dijkstry i Bellmana-Forda?

Studiowałem te trzy i poniżej przedstawiam swoje wnioski. Czy ktoś mógłby mi powiedzieć, czy dobrze je zrozumiałem, czy nie? Dziękuję Ci.

1. Dijkstra algorytm jest używany tylko wtedy, gdy masz jedno źródło i chcesz wiedzieć najmniejszą ścieżkę z jednego węzła do drugiego, ale nie w przypadkach takich jak ten .

2. Algorytm Floyda-Warshalla jest używany, gdy dowolny ze wszystkich węzłów może być źródłem, więc chcesz, aby najkrótsza odległość dotarła do dowolnego węzła docelowego z dowolnego węzła źródłowego. Nie udaje się to tylko wtedy, gdy występują cykle ujemne.

3. Bellman-Ford jest używany jak Dijkstra, gdy jest tylko jedno źródło. Może to obsługiwać ujemne wagi, a jego działanie jest takie samo jak Floyd-Warshall, z wyjątkiem jednego źródła, prawda? (To jest ten, którego jestem najmniej pewny.)

Algorytm Dijkstry jest używany tylko wtedy, gdy masz jedno źródło i chcesz poznać najmniejszą ścieżkę z jednego węzła do drugiego, ale zawodzi [na wykresach z ujemnymi krawędziami]

$s$$s$previous[v]$v$

Zachowanie algorytmu Dijkstry na wykresach z ujemnymi krawędziami zależy od dokładnie omawianego wariantu. Niektóre warianty algorytmu, takie jak ten w Wikipedii, zawsze działają szybko, ale nie obliczają poprawnie najkrótszych ścieżek, gdy występują ujemne krawędzie. Inne warianty, takie jak ten w notatkach z wykładów, zawsze poprawnie obliczają najkrótsze ścieżki (chyba że istnieje ujemny cykl dostępny ze źródła), ale w najgorszym przypadku mogą wymagać czasu wykładniczego, jeśli występują ujemne krawędzie.

Algorytm Floyda-Warshalla jest używany, gdy dowolny ze wszystkich węzłów może być źródłem, więc chcesz, aby najkrótsza odległość dotarła do dowolnego węzła docelowego z dowolnego węzła źródłowego. Nie udaje się to tylko wtedy, gdy występują cykle ujemne.

To jest poprawne. Floyd-Warshall jest jednym z przykładów algorytmu najkrótszej ścieżki złożonej z wszystkich par , co oznacza, że ​​oblicza najkrótsze ścieżki między każdą parą węzłów. Innym przykładem jest „dla każdego węzła v uruchom Dijkstra z v jako węzłem źródłowym”. Istnieje kilka innych.

Bellman-Ford jest używany jak Dijkstra, gdy jest tylko jedno źródło. Może to obsługiwać ujemne wagi, a jego działanie jest takie samo jak Floyda-Warshalla, z wyjątkiem jednego źródła, prawda?

$O(V^3)$$O(V^2E)$$O(VE)$

Aby uzyskać więcej informacji, zapoznaj się z podręcznikiem ulubionych algorytmów. (Robisz mieć ulubione algorytmy podręcznik, prawda?)

Wszystkie trzy algorytmy są omówione na slajdach wykładowych prof. Jaehyun Park (Uniwersytet Stanforda). Oto link Algorytmy najkrótszej ścieżki

Strona Wikipedii dotycząca problemu najkrótszej ścieżki opisuje dwa różne problemy: SSSP i APSP.

Najkrótsza ścieżka z jednego źródła (SSSP):

• Algorytm Dijkstry: rozwiązuje problem najkrótszej ścieżki z jednego źródła.
• • Ograniczenia: Tylko krawędzie ujemne, z którymi nie może sobie poradzić.
• • Nieważone wykresy: Dijkstra's jest taki sam jak BFS.

• Algorytm Bellmana-Forda: rozwiązuje problem jednego źródła, jeśli wagi krawędzi mogą być ujemne. Jest to poprawa w przypadku Dijkstry, gdzie jest teraz w stanie poradzić sobie również z ujemnymi wagami.

Wszystkie pary najkrótsza ścieżka (APSP):

• Algorytm Floyda – Warshalla: rozwiązuje wszystkie pary najkrótszych ścieżek. Obsługuje zarówno dodatnie, jak i ujemne krawędzie.
• • Ograniczenia: Nie można obsłużyć cykli ujemnych.

Stąd Floyd – Warshall nie jest tym samym co BFS, chociaż podstawową metodologią jest to samo, programowanie dynamiczne.

Być może powinien to być komentarz, a nie odpowiedź, ale jest to różnica między tymi algorytmami, o których inne odpowiedzi nie wspominają.

Ludzie nazywają algorytm Floyda Floyd-Warshall , ale algorytmy Floyda i Warshalla nie są takie same.

$O(1)$$O(n^2)$