- Bieżący
- Ma odległość
- Użyta krawędź
- Ścieżka
- Cykl ujemny
Algorytm Bellmana–Forda
Algorytm Dijkstry zawodzi, gdy krawędź ma ujemną długość, jak droga, która zamiast pobierać opłatę, sama ci płaci. Algorytm Bellmana–Forda nie zawodzi: po prostu sprawdza każdą krawędź raz po raz, aż nic się nie poprawia, i potrafi nawet wykryć, że jakiś cykl sprawia, że odległości maleją bez końca. Kliknij wierzchołek, aby od niego zacząć, i przejdź przez kolejne przebiegi krok po kroku. Naciśnij Odtwórz, aby śledzić wyszukiwanie, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Każda krawędź jest jednokierunkowa, jak pokazuje strzałka, a liczba na niej to jej długość, która może być ujemna. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby na końcu zobaczyć najkrótszą ścieżkę do niego. Liczba na każdym wierzchołku to jego dotychczasowa odległość. Zaznacz Dodaj cykl ujemny, aby zobaczyć, jak algorytm Bellmana–Forda go znajduje. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Kliknij wierzchołek, aby uczynić go startem. Aby na końcu zobaczyć ścieżkę, przełącz kliknięcie na Cel i kliknij inny wierzchołek.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
- Zaznacz Dodaj cykl ujemny, aby zobaczyć, jak algorytm Bellmana–Forda go znajduje. Nowy graf tworzy inny graf do wypróbowania.
Jak działa algorytm Bellmana–Forda
Daj startowi odległość 0, a każdemu innemu wierzchołkowi nieskończoność. Potem wykonuj przebiegi: w każdym przebiegu sprawdź raz każdą krawędź u → v. Jeśli u ma odległość, a dist(u) plus długość krawędzi to mniej niż dist(v), obniż dist(v) i zapamiętaj u jako drogę do v. Po przebiegu k znana jest każda najkrótsza ścieżka, która używa co najwyżej k krawędzi. Najkrótsza ścieżka odwiedza każdy wierzchołek co najwyżej raz, więc ma co najwyżej n − 1 krawędzi, a n − 1 przebiegów zawsze wystarcza. Jeśli cały przebieg niczego nie zmienia, wyszukiwanie może skończyć się wcześniej.
Wykrywanie cyklu ujemnego
Jeśli krawędzie cyklu sumują się do mniej niż zera, każde kolejne okrążenie cyklu skraca ścieżkę, więc najkrótszej ścieżki w ogóle nie ma. Algorytm Bellmana–Forda to zauważa: po n − 1 przebiegach jeszcze jeden przebieg nie powinien niczego zmienić. Jeśli jakąś krawędź wciąż da się zrelaksować, ze startu osiągalny jest cykl ujemny, a cofając się od tej krawędzi po zapamiętanych wierzchołkach, trafia się do niego. W aplikacji cykl jest rysowany na czerwono.
Często zadawane pytania
Czym jest algorytm Bellmana–Forda?
Algorytmem, który znajduje najkrótsze ścieżki od jednego startu do wszystkich innych wierzchołków w grafie, którego krawędzie mogą mieć ujemne długości. Relaksuje każdą krawędź w powtarzanych przebiegach i zgłasza cykl ujemny, jeśli da się do niego dojść ze startu.
Dlaczego algorytm Dijkstry zawodzi przy ujemnych krawędziach?
Dijkstra uznaje odległość wierzchołka za ostateczną, gdy tylko jest on najbliższy w kolejce. Ujemna krawędź znaleziona później może jeszcze prowadzić z powrotem do tego wierzchołka krótszą drogą, więc ostateczna odległość może być błędna. Algorytm Bellmana–Forda nigdy nie uznaje odległości za ostateczną zbyt wcześnie; sprawdza każdą krawędź dalej.
Dlaczego n − 1 przebiegów?
Najkrótsza ścieżka nigdy nie musi odwiedzać wierzchołka dwa razy, więc ma co najwyżej n − 1 krawędzi. Każdy przebieg wydłuża znane najkrótsze ścieżki o co najmniej jedną krawędź, więc po n − 1 przebiegach wszystkie są znalezione.
Jak szybki jest algorytm Bellmana–Forda?
Każdy przebieg sprawdza wszystkie E krawędzi, a przebiegów jest co najwyżej V − 1, więc praca rośnie jak V × E. To wolniej niż algorytm Dijkstry, dlatego algorytmu Bellmana–Forda używa się, gdy krawędzie mogą być ujemne.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i jest przeszukiwany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora