Algorytm Bellmana-Forda
Ostatnia aktualizacja
Algorytm Bellmana-Forda znajduje najkrótszą ścieżkę od węzła źródłowego do każdego innego węzła i w przeciwieństwie do algorytmu Dijkstry działa nawet wtedy, gdy niektóre wagi krawędzi są ujemne. Opiera się na relaksacji metodą siłową: wielokrotnie przegląda każdą krawędź i jeśli przejście przez nią daje krótszą odległość, aktualizuje odległość węzła docelowego. Kliknij odtwarzanie powyżej i zobacz, jak tymczasowe odległości maleją z każdym przebiegiem.
Po V - 1 przebiegach przez wszystkie krawędzie każda najkrótsza ścieżka (która może mieć najwyżej V - 1 krawędzi) jest już znaleziona. Daje to złożoność O(V · E): wolniej niż Dijkstra, ale algorytm obsługuje ujemne wagi i potrafi wykryć cykl o ujemnej wadze (jeśli przebieg numer V wciąż relaksuje krawędź, najkrótsza ścieżka nie istnieje).
Złożoność czasowa i pamięciowa
| Miara | Złożoność | Uwagi |
|---|---|---|
| Czas | O(V · E) | V − 1 przebiegów przez wszystkie E krawędzi |
| Pamięć | O(V) | Jedna odległość na węzeł |
| Ujemne wagi | Obsługiwane | Główna przewaga nad algorytmem Dijkstry |
| Ujemne cykle | Wykrywalne | Relaksacja w przebiegu numer V oznacza cykl |
Krok po kroku
| Krok | Co się dzieje |
|---|---|
| 1 | Ustaw odległość źródła na 0, a wszystkich pozostałych na nieskończoność. |
| 2 | Powtórz następny krok V − 1 razy. |
| 3 | Dla każdej krawędzi (u → v, w) sprawdź, czy dist[u] + w < dist[v]. |
| 4 | Jeśli tak, zrelaksuj ją: ustaw dist[v] = dist[u] + w. |
| 5 | Zakończ wcześniej, jeśli pełny przebieg niczego nie zmienia. |
Przykład krok po kroku
Źródło S w grafie z 4 węzłami S, A, B, C i krawędziami S→A (4), S→B (5), A→C (3), B→A (-3), relaksowanymi w tej kolejności. Odległości startują od S=0, a wszystkie pozostałe od ∞:
| Przebieg | Odległości [S, A, B, C] | Działanie |
|---|---|---|
| Start | [0, ∞, ∞, ∞] | Odległość źródła to 0, wszystkich pozostałych nieskończoność. |
| 1 | [0, 2, 5, 7] | Relaksuj S→A do 4, S→B do 5, A→C do 7, potem B→A obniża A do 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C poprawia teraz C do 2 + 3 = 5; żadna inna krawędź się nie relaksuje. |
| 3 | [0, 2, 5, 5] | Żadna krawędź się nie relaksuje, więc odległości są ostateczne: A kosztuje 2 przez S→B→A. |
Kiedy używać algorytmu Bellmana-Forda
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Wagi krawędzi mogą być ujemne. | Wszystkie wagi są nieujemne (Dijkstra jest szybszy). |
| Musisz wykrywać cykle o ujemnej wadze. | Graf jest ogromny i gęsty: O(V · E) to za wolno. |
| Graf jest mały lub rzadki. | Potrzebujesz tylko jednego zapytania od źródła do celu w dużym grafie. |
| Potrzebujesz prostego, łatwego w implementacji punktu odniesienia. | Wagi są nieujemne, a liczy się czas odpowiedzi. |
Bellman-Ford Algorithm: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Bellman-Ford Algorithm w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Bellman-Ford Algorithm: kod (Python)
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Bellman-Ford Algorithm: kod (JavaScript)
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Bellman-Ford Algorithm: kod (Java)
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Bellman-Ford Algorithm: kod (C++)
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Bellman-Ford Algorithm: kod (C)
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}Algorytm Bellmana-Forda: najczęstsze pytania
Jaka jest złożoność czasowa algorytmu Bellmana-Forda?
Algorytm Bellmana-Forda działa w czasie
O(V · E): wykonuje V - 1 przebiegów, a każdy przebieg relaksuje wszystkie E krawędzi. To wolniej niż O((V + E) log V) algorytmu Dijkstry i jest to cena obsługi ujemnych wag krawędzi.Kiedy użyć algorytmu Bellmana-Forda zamiast Dijkstry?
Użyj algorytmu Bellmana-Forda, gdy graf może mieć ujemne wagi krawędzi albo gdy musisz wykrywać cykle o ujemnej wadze. Dijkstra jest szybszy, ale działa poprawnie tylko przy nieujemnych wagach. Typowe praktyczne zastosowanie to wykrywanie arbitrażu walutowego, gdzie ujemne cykle mają znaczenie.
Jak algorytm Bellmana-Forda wykrywa ujemny cykl?
Po
V - 1 przebiegach relaksacji wszystkie najkrótsze ścieżki są ustalone, o ile nie ma ujemnego cyklu. Jeśli jeszcze jeden przebieg wciąż może zrelaksować krawędź, to osiągalny jest cykl o ujemnej wadze, a najkrótsze ścieżki są nieokreślone (można by krążyć w nieskończoność i obniżać koszt).Czym różni się algorytm Bellmana-Forda od algorytmu Floyda-Warshalla?
Algorytm Bellmana-Forda wyznacza najkrótsze ścieżki z jednego źródła w
O(V · E), a Floyd-Warshall wyznacza najkrótsze ścieżki między wszystkimi parami w O(V³). W gęstym grafie uruchomienie Bellmana-Forda z każdego źródła kosztuje O(V² · E), więc gdy potrzebujesz każdej pary, Floyd-Warshall jest zwykle lepszym wyborem. Oba obsługują ujemne krawędzie i potrafią zgłosić ujemne cykle.Dlaczego algorytm Bellmana-Forda potrzebuje dokładnie V - 1 przebiegów?
Każda najkrótsza ścieżka w grafie bez ujemnych cykli używa najwyżej
V - 1 krawędzi, bo ścieżka odwiedzająca więcej niż V węzłów musi któryś powtórzyć. Każdy przebieg gwarantuje poprawną relaksację co najmniej jednej kolejnej krawędzi każdej najkrótszej ścieżki, więc V - 1 przebiegów wystarcza, by ustalić je wszystkie. Częste nieporozumienie: więcej przebiegów nie poprawia wyniku, chyba że istnieje ujemny cykl.Czy algorytm Bellmana-Forda może zakończyć się wcześniej?
Tak. Jeśli pełny przebieg przez wszystkie krawędzie niczego nie relaksuje, każda odległość jest już optymalna i można przerwać przed osiągnięciem
V - 1 przebiegów. Ta optymalizacja często znacznie przyspiesza działanie na grafach, które szybko się zbiegają, choć ograniczenie w najgorszym przypadku pozostaje O(V · E).Powiązane materiały
Więcej wizualizacji
