PL 
EnglishDomyślny
Українська🗺️ Algorytm Bellmana-Forda — najkrótsze ścieżki z ujemnymi wagami
Obserwuj, jak Bellman-Ford relaksuje każdą krawędź V−1 razy, by znaleźć najkrótsze ścieżki od źródła, nawet z ujemnymi wagami, a następnie wykonuje jeszcze jeden przebieg, by wykryć ujemne cykle.
O tej symulacji
Algorytm Bellmana-Forda, opracowany niezależnie przez Richarda Bellmana (1958) i Lestera Forda Jr. (1956), oblicza najkrótsze ścieżki od pojedynczego wierzchołka źródłowego do wszystkich pozostałych wierzchołków w ważonym grafie skierowanym. W przeciwieństwie do algorytmu Dijkstry toleruje ujemne wagi krawędzi.
🔬 Co pokazuje
Ważony graf skierowany, na którym każda krawędź jest relaksowana w kolejnych przebiegach, aż wszystkie odległości od źródła się ustabilizują.
🎮 Jak korzystać
Wybierz przykładowy graf i uruchom algorytm w trybie automatycznym lub krok po kroku, obserwując aktualizacje odległości przy każdej relaksacji.
💡 Czy wiesz, że…
Dodatkowy, V-ty przebieg po wszystkich krawędziach służy wyłącznie do wykrywania ujemnych cykli — jeśli którakolwiek odległość nadal może się poprawić, graf zawiera cykl o ujemnej wadze osiągalny ze źródła.
Często zadawane pytania
Dlaczego Bellman-Ford potrzebuje V−1 przebiegów?
Ponieważ najdłuższa możliwa najkrótsza ścieżka w grafie z V wierzchołkami (nie powtarzająca wierzchołka) może mieć co najwyżej V−1 krawędzi. Każdy pełny przebieg po wszystkich krawędziach gwarantuje, że co najmniej jedna kolejna krawędź na każdej najkrótszej ścieżce zostanie ustalona.
Jak Bellman-Ford wykrywa ujemne cykle?
Po wymaganych V−1 przebiegach algorytm wykonuje jeszcze jeden przebieg po wszystkich krawędziach. Jeśli którąkolwiek krawędź nadal można zrelaksować, oznacza to istnienie cyklu o ujemnej wadze osiągalnego ze źródła.
Jak Bellman-Ford wypada w porównaniu z algorytmem Dijkstry?
Oba obliczają najkrótsze ścieżki z jednego źródła, ale Dijkstra używa zachłannej kolejki priorytetowej i wymaga nieujemnych wag, działając w czasie O((V+E) log V). Bellman-Ford relaksuje każdą krawędź w każdym przebiegu, toleruje ujemne wagi i wykrywa ujemne cykle, kosztem wolniejszego czasu O(V·E).
Czy Bellman-Ford radzi sobie z grafami nieskierowanymi z ujemnymi krawędziami?
Nie. Każda nieskierowana krawędź o ujemnej wadze jest równoważna dwuwierzchołkowemu ujemnemu cyklowi (u→v i v→u), więc Bellman-Ford natychmiast oznaczyłby ją jako ujemny cykl.