Wyobraź sobie, że masz mapę z różnymi miastami połączonymi drogami, przy czym każda droga ma określoną odległość. The Algorytm Bellmana-Forda jest jak przewodnik, który pomaga znaleźć najkrótszą ścieżkę z jednego miasta do wszystkich innych miast, nawet jeśli niektóre drogi mają ujemną długość. To jest jak GPS dla komputerów, przydatne do znalezienia najszybszego sposobu przedostania się z jednego punktu do drugiego w sieci. W tym artykule przyjrzymy się bliżej, jak działa ten algorytm i dlaczego jest tak przydatny w rozwiązywaniu codziennych problemów.
Spis treści
- Algorytm Bellmana-Forda
- Idea algorytmu Bellmana Forda
- Zasada relaksacji krawędzi dla Bellmana-Forda
- Dlaczego relaksujące krawędzie N-1 razy dają nam najkrótszą ścieżkę z jednego źródła?
- Dlaczego zmniejszenie odległości w N-tej relaksacji wskazuje na istnienie ujemnego cyklu?
- Działanie algorytmu Bellmana-Forda do wykrywania cyklu ujemnego na wykresie
- Algorytm znajdowania cyklu ujemnego na ukierunkowanym grafie ważonym przy użyciu metody Bellmana-Forda
- Obsługa rozłączonych grafów w algorytmie
- Analiza złożoności algorytmu Bellmana-Forda
- Zastosowania algorytmów Bellmana Forda
- Wady algorytmu Bellmana Forda
Algorytm Bellmana-Forda
Bellman-Ford jest pojedyncze źródło algorytm najkrótszej ścieżki, który wyznacza najkrótszą ścieżkę pomiędzy danym wierzchołkiem źródłowym a każdym innym wierzchołkiem grafu. Algorytm ten może być stosowany w obu przypadkach ważony I nieważony wykresy.
różnica między lisem a wilkiem
A Bellman-Ford algorytm gwarantuje również znalezienie najkrótszej ścieżki na wykresie, podobnie jak Algorytm Dijkstry . Chociaż Bellman-Ford jest wolniejszy niż Algorytm Dijkstry , jest w stanie obsługiwać wykresy ujemne wagi krawędzi co czyni go bardziej uniwersalnym. Nie można znaleźć najkrótszej ścieżki, jeśli istnieje a cykl negatywny na wykresie. Jeśli będziemy nadal okrążać cykl ujemny nieskończoną liczbę razy, koszt ścieżki będzie nadal spadać (nawet jeśli długość ścieżki będzie rosnąć). W rezultacie, Bellman-Ford jest również w stanie wykryć cykle ujemne , co jest ważną cechą.
Idea algorytmu Bellmana Forda:
Podstawową zasadą algorytmu Bellmana-Forda jest to, że rozpoczyna się od jednego źródła i oblicza odległość do każdego węzła. Odległość jest początkowo nieznana i zakłada się, że jest nieskończona, ale w miarę upływu czasu algorytm rozluźnia te ścieżki, identyfikując kilka krótszych ścieżek. Stąd mówi się, że na nim opiera się Bellman-Ford Zasada relaksu .
Zasada relaksacji krawędzi dla Bellmana-Forda:
- Stwierdza, że dla grafu posiadającego N wierzchołkach, wszystkie krawędzie powinny być rozluźnione N-1 razy, aby obliczyć najkrótszą ścieżkę z jednego źródła.
- Aby wykryć, czy istnieje cykl ujemny, należy jeszcze raz rozluźnić wszystkie krawędzie i jeśli najkrótsza odległość dla dowolnego węzła ulegnie zmniejszeniu, możemy powiedzieć, że istnieje cykl ujemny. Krótko mówiąc, jeśli rozluźnimy krawędzie N razy i występuje jakakolwiek zmiana w najkrótszej odległości dowolnego węzła pomiędzy N-1 I N-ty relaksacja niż istnieje cykl ujemny, w przeciwnym razie nie istnieje.
Dlaczego relaksujące krawędzie N-1 razy dają nam najkrótszą ścieżkę z jednego źródła?
W najgorszym przypadku najkrótsza ścieżka między dwoma wierzchołkami może mieć co najwyżej N-1 krawędzie, gdzie N jest liczbą wierzchołków. Dzieje się tak, ponieważ prosta ścieżka na wykresie z N wierzchołki mogą mieć co najwyżej N-1 krawędzie, ponieważ nie da się utworzyć zamkniętej pętli bez ponownego odwiedzenia wierzchołka.
Poprzez rozluźnienie krawędzi N-1 razy algorytm Bellmana-Forda zapewnia, że szacunki odległości dla wszystkich wierzchołków zostały zaktualizowane do wartości optymalnych, zakładając, że graf nie zawiera żadnych cykli o ujemnych wagach osiągalnych z wierzchołka źródłowego. Jeśli graf zawiera cykl o ujemnej wadze osiągalny z wierzchołka źródłowego, algorytm może go wykryć później N-1 iteracje, ponieważ cykl ujemny zakłóca najkrótsze ścieżki.
Podsumowując, relaksujące krawędzie N-1 razy w algorytmie Bellmana-Forda gwarantuje, że algorytm zbadał wszystkie możliwe ścieżki o długości do N-1 , czyli maksymalna możliwa długość najkrótszej ścieżki w grafie N wierzchołki. Pozwala to algorytmowi poprawnie obliczyć najkrótsze ścieżki od wierzchołka źródłowego do wszystkich pozostałych wierzchołków, biorąc pod uwagę, że nie ma cykli o wadze ujemnej.
Dlaczego zmniejszenie odległości w N-tej relaksacji wskazuje na istnienie ujemnego cyklu?
Jak wspomniano wcześniej, osiągnięcie najkrótszej ścieżki z jednego źródła do wszystkich pozostałych węzłów zajmuje N-1 relaksacje. Jeśli N-ta relaksacja dodatkowo zmniejsza najkrótszą odległość dla dowolnego węzła, oznacza to, że pewna krawędź o ujemnej wadze została ponownie przekroczona. Warto zaznaczyć, że w trakcie N-1 relaksacji zakładaliśmy, że każdy wierzchołek przechodzi tylko raz. Jednakże zmniejszenie odległości podczas N-tej relaksacji oznacza powrót do wierzchołka.
Działanie algorytmu Bellmana-Forda wykrywającego cykl ujemny na wykresie:
Załóżmy, że mamy wykres podany poniżej i chcemy sprawdzić, czy istnieje cykl ujemny, czy też nie, korzystając z Bellmana-Forda.
Wykres początkowy
tablica obiektów w JavieKrok 1: Zainicjuj tablicę odległości Dist[], aby przechowywać najkrótszą odległość dla każdego wierzchołka od wierzchołka źródłowego. Początkowo odległość źródła będzie wynosić 0, a odległość innych wierzchołków będzie NIESKOŃCZONOŚĆ.
Zainicjuj tablicę odległości
Krok 2: Rozpocznij rozluźnianie krawędzi podczas I Relaksacji:
- Aktualna odległość B> (odległość A) + (waga A do B), tj. nieskończoność> 0 + 5
- Zatem Odległość[B] = 5
1. Relaks
Krok 3: Podczas 2. Relaksacji:
- Aktualna odległość D> (odległość B) + (waga B do D), tj. nieskończoność> 5 + 2
- Odległość[D] = 7
- Aktualna odległość C> (odległość B) + (waga B do C), tj. nieskończoność> 5 + 1
- Odległość[C] = 6
2. Relaks
Krok 4: Podczas trzeciego relaksu:
- Aktualna odległość F> (odległość D) + (waga D do F), tj. nieskończoność> 7 + 2
- Odległość[F] = 9
- Aktualna odległość E> (odległość C) + (waga C do E), tj. nieskończoność> 6 + 1
- Odległość[E] = 7
Trzeci relaks
Zastępowanie metody w JavieKrok 5: Podczas IV Relaksu:
- Aktualna odległość D> (odległość E) + (waga E do D), tj. 7> 7 + (-1)
- Odległość[D] = 6
- Aktualna odległość E> (Odległość F ) + (Waga F do E), tj. 7> 9 + (-3)
- Odległość[E] = 6
4. Relaks
Krok 6: Podczas V Relaksu:
- Aktualna odległość F> (odległość D) + (waga D do F), tj. 9> 6 + 2
- Odległość[F] = 8
- Aktualna odległość D> (Odległość E ) + (Waga E do D), tj. 6> 6 + (-1)
- Odległość[D] = 5
- Ponieważ graf ma 6 wierzchołków, zatem podczas 5. relaksacji należało obliczyć najkrótszą odległość dla wszystkich wierzchołków.
5. Relaks
Krok 7: Teraz ostatnia relaksacja, tj. 6. relaksacja, powinna wskazywać na obecność ujemnego cyklu, jeśli wystąpią jakiekolwiek zmiany w tablicy odległości 5. relaksacji.
Podczas 6. relaksacji można zaobserwować następujące zmiany:
- Aktualna odległość E> (odległość F) + (waga F do E), tj. 6> 8 + (-3)
- Odległość[E]=5
- Aktualna odległość F> (Odległość D ) + (Waga D do F), tj. 8> 5 + 2
- Odległość[F]=7
Ponieważ obserwujemy zmiany w tablicy Distance, możemy zatem stwierdzić obecność ujemnego cyklu na wykresie.
6. Relaks
FCFSWynik: Na wykresie występuje cykl ujemny (D->F->E).
Algorytm znajdowania ujemnego cyklu na ukierunkowanym grafie ważonym przy użyciu metody Bellmana-Forda:
- Zainicjuj tablicę odległości dist[] dla każdego wierzchołka „ W ' Jak odległość[v] = NIESKOŃCZONOŚĆ .
- Przyjmij dowolny wierzchołek (powiedzmy „0”) jako źródło i przypisz odległość = 0 .
- Zrelaksuj się krawędzie(u,v,waga) N-1 razy zgodnie z poniższym warunkiem:
- odległość[v] = minimalna(odległość[v], odległość[u] + waga)
- Teraz jeszcze raz rozluźnij wszystkie krawędzie, tj N-ty czasu i na podstawie poniższych dwóch przypadków możemy wykryć cykl ujemny:
- Przypadek 1 (istnieje cykl ujemny): Dla dowolnego krawędź (u, v, waga), jeśli odległość [u] + waga
- Przypadek 2 (cykl bez ujemnego): przypadek 1 kończy się niepowodzeniem dla wszystkich krawędzi.
- Przypadek 1 (istnieje cykl ujemny): Dla dowolnego krawędź (u, v, waga), jeśli odległość [u] + waga
Obsługa rozłączonych wykresów w algorytmie:
Powyższy algorytm i program mogą nie działać w przypadku rozłączenia danego wykresu. Działa, gdy wszystkie wierzchołki są osiągalne z wierzchołka źródłowego 0 .
Aby obsłużyć rozłączone grafy, możemy powtórzyć powyższy algorytm dla wierzchołków mających odległość = NIESKOŃCZONOŚĆ, lub po prostu dla wierzchołków, które nie są odwiedzane.
Poniżej implementacja powyższego podejścia:
C++ // A C++ program for Bellman-Ford's single source // shortest path algorithm. #include using namespace std; // a structure to represent a weighted edge in graph struct Edge { int src, dest, weight; }; // a structure to represent a connected, directed and // weighted graph struct Graph { // V->Liczba wierzchołków, E-> Liczba krawędzi int V, E; // wykres jest reprezentowany jako tablica krawędzi. konstrukcja Krawędź* krawędź; }; // Tworzy graf z wierzchołkami V i krawędziami E struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph; wykres->V = V; wykres->E = E; wykres->krawędź = nowa Krawędź[E]; wykres zwrotu; } // Funkcja narzędziowa używana do wydrukowania rozwiązania void printArr(int dist[], int n) { printf('Odległość wierzchołka od źródła
'); for (int i = 0; tj< n; ++i) printf('%d %d
', i, dist[i]); } // The main function that finds shortest distances from src // to all other vertices using Bellman-Ford algorithm. The // function also detects negative weight cycle void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = wykres->E; int odległość[V]; // Krok 1: Zainicjuj odległości od src do wszystkich pozostałych // wierzchołków jako NIESKOŃCZONE dla (int i = 0; i< V; i++) dist[i] = INT_MAX; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can have // at-most |V| - 1 edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->krawędź[j].src; int v = wykres->krawędź[j].dest; int waga = wykres->krawędź[j].waga; if (odległość[u] != INT_MAX && odległość[u] + waga< dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The above // step guarantees shortest distances if graph doesn't // contain negative weight cycle. If we get a shorter // path, then there is a cycle. for (int i = 0; i < E; i++) { int u = graph->krawędź[i].src; int v = wykres->krawędź[i].dest; int waga = wykres->krawędź[i].waga; if (odległość[u] != INT_MAX && odległość[u] + waga< dist[v]) { printf('Graph contains negative weight cycle'); return; // If negative cycle is detected, simply // return } } printArr(dist, V); return; } // Driver's code int main() { /* Let us create the graph given in above example */ int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph struct Graph* graph = createGraph(V, E); // add edge 0-1 (or A-B in above figure) graph->krawędź[0].src = 0; wykres->krawędź[0].dest = 1; wykres->krawędź[0].waga = -1; // dodaj krawędź 0-2 (lub A-C na powyższym rysunku) graph->edge[1].src = 0; wykres->krawędź[1].dest = 2; wykres->krawędź[1].waga = 4; // dodaj krawędź 1-2 (lub B-C na powyższym rysunku) graph->edge[2].src = 1; wykres->krawędź[2].dest = 2; wykres->krawędź[2].waga = 3; // dodaj krawędź 1-3 (lub B-D na powyższym rysunku) graph->edge[3].src = 1; wykres->krawędź[3].dest = 3; wykres->krawędź[3].waga = 2; // dodaj krawędź 1-4 (lub B-E na powyższym rysunku) graph->edge[4].src = 1; wykres->krawędź[4].dest = 4; wykres->krawędź[4].waga = 2; // dodaj krawędź 3-2 (lub D-C na powyższym rysunku) graph->edge[5].src = 3; wykres->krawędź[5].dest = 2; wykres->krawędź[5].waga = 5; // dodaj krawędź 3-1 (lub D-B na powyższym rysunku) graph->edge[6].src = 3; wykres->krawędź[6].dest = 1; wykres->krawędź[6].waga = 1; // dodaj krawędź 4-3 (lub E-D na powyższym rysunku) graph->edge[7].src = 4; wykres->krawędź[7].dest = 3; wykres->krawędź[7].waga = -3; // Wywołanie funkcji BellmanFord(graph, 0); zwróć 0; }> Jawa // A Java program for Bellman-Ford's single source shortest // path algorithm. import java.io.*; import java.lang.*; import java.util.*; // A class to represent a connected, directed and weighted // graph class Graph { // A class to represent a weighted edge in graph class Edge { int src, dest, weight; Edge() { src = dest = weight = 0; } }; int V, E; Edge edge[]; // Creates a graph with V vertices and E edges Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } // The main function that finds shortest distances from // src to all other vertices using Bellman-Ford // algorithm. The function also detects negative weight // cycle void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int dist[] = new int[V]; // Step 1: Initialize distances from src to all // other vertices as INFINITE for (int i = 0; i < V; ++i) dist[i] = Integer.MAX_VALUE; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The // above step guarantees shortest distances if graph // doesn't contain negative weight cycle. If we get // a shorter path, then there is a cycle. for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) { System.out.println( 'Graph contains negative weight cycle'); return; } } printArr(dist, V); } // A utility function used to print the solution void printArr(int dist[], int V) { System.out.println('Vertex Distance from Source'); for (int i = 0; i < V; ++i) System.out.println(i + ' ' + dist[i]); } // Driver's code public static void main(String[] args) { int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; // Function call graph.BellmanFord(graph, 0); } } // Contributed by Aakash Hasija> Python3 # Python3 program for Bellman-Ford's single source # shortest path algorithm. # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print('Vertex Distance from Source') for i in range(self.V): print('{0} {1}'.format(i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float('Inf')] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for _ in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float('Inf') and dist[u] + w < dist[v]: print('Graph contains negative weight cycle') return # print all distance self.printArr(dist) # Driver's code if __name__ == '__main__': g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # function call g.BellmanFord(0) # Initially, Contributed by Neelam Yadav # Later On, Edited by Himanshu Garg> C# // C# program for Bellman-Ford's single source shortest // path algorithm. using System; // A class to represent a connected, directed and weighted // graph class Graph { // A class to represent a weighted edge in graph class Edge { public int src, dest, weight; public Edge() { src = dest = weight = 0; } }; int V, E; Edge[] edge; // Creates a graph with V vertices and E edges Graph(int v, int e) { V = v; E = e; edge = new Edge[e]; for (int i = 0; i < e; ++i) edge[i] = new Edge(); } // The main function that finds shortest distances from // src to all other vertices using Bellman-Ford // algorithm. The function also detects negative weight // cycle void BellmanFord(Graph graph, int src) { int V = graph.V, E = graph.E; int[] dist = new int[V]; // Step 1: Initialize distances from src to all // other vertices as INFINITE for (int i = 0; i < V; ++i) dist[i] = int.MaxValue; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i < V; ++i) { for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The // above step guarantees shortest distances if graph // doesn't contain negative weight cycle. If we get // a shorter path, then there is a cycle. for (int j = 0; j < E; ++j) { int u = graph.edge[j].src; int v = graph.edge[j].dest; int weight = graph.edge[j].weight; if (dist[u] != int.MaxValue && dist[u] + weight < dist[v]) { Console.WriteLine( 'Graph contains negative weight cycle'); return; } } printArr(dist, V); } // A utility function used to print the solution void printArr(int[] dist, int V) { Console.WriteLine('Vertex Distance from Source'); for (int i = 0; i < V; ++i) Console.WriteLine(i + ' ' + dist[i]); } // Driver's code public static void Main() { int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph Graph graph = new Graph(V, E); // add edge 0-1 (or A-B in above figure) graph.edge[0].src = 0; graph.edge[0].dest = 1; graph.edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph.edge[2].src = 1; graph.edge[2].dest = 2; graph.edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph.edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph.edge[4].src = 1; graph.edge[4].dest = 4; graph.edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph.edge[5].src = 3; graph.edge[5].dest = 2; graph.edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph.edge[6].src = 3; graph.edge[6].dest = 1; graph.edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph.edge[7].src = 4; graph.edge[7].dest = 3; graph.edge[7].weight = -3; // Function call graph.BellmanFord(graph, 0); } // This code is contributed by Ryuga }> JavaScript // a structure to represent a connected, directed and // weighted graph class Edge { constructor(src, dest, weight) { this.src = src; this.dest = dest; this.weight = weight; } } class Graph { constructor(V, E) { this.V = V; this.E = E; this.edge = []; } } function createGraph(V, E) { const graph = new Graph(V, E); for (let i = 0; i < E; i++) { graph.edge[i] = new Edge(); } return graph; } function printArr(dist, V) { console.log('Vertex Distance from Source'); for (let i = 0; i < V; i++) { console.log(`${i} ${dist[i]}`); } } function BellmanFord(graph, src) { const V = graph.V; const E = graph.E; const dist = []; for (let i = 0; i < V; i++) { dist[i] = Number.MAX_SAFE_INTEGER; } dist[src] = 0; for (let i = 1; i <= V - 1; i++) { for (let j = 0; j < E; j++) { const u = graph.edge[j].src; const v = graph.edge[j].dest; const weight = graph.edge[j].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } for (let i = 0; i < E; i++) { const u = graph.edge[i].src; const v = graph.edge[i].dest; const weight = graph.edge[i].weight; if (dist[u] !== Number.MAX_SAFE_INTEGER && dist[u] + weight < dist[v]) { console.log('Graph contains negative weight cycle'); return; } } printArr(dist, V); } // Driver program to test methods of graph class // Create a graph given in the above diagram const V = 5; const E = 8; const graph = createGraph(V, E); graph.edge[0] = new Edge(0, 1, -1); graph.edge[1] = new Edge(0, 2, 4); graph.edge[2] = new Edge(1, 2, 3); graph.edge[3] = new Edge(1, 3, 2); graph.edge[4] = new Edge(1, 4, 2); graph.edge[5] = new Edge(3, 2, 5); graph.edge[6] = new Edge(3, 1, 1); graph.edge[7] = new Edge(4, 3, -3); BellmanFord(graph, 0);> Wyjście
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>
Analiza złożoności algorytmu Bellmana-Forda :
- Złożoność czasowa, gdy wykres jest połączony:
- Najlepszy przypadek: O(E), gdy tablica odległości po pierwszej i drugiej relaksacji jest taka sama, możemy po prostu przerwać dalsze przetwarzanie
- Przeciętny przypadek: O(V*E)
- Najgorszy przypadek: O(V*E)
- Złożoność czasowa, gdy wykres jest odłączony :
- Wszystkie przypadki: O(E*(V^2))
- Przestrzeń pomocnicza: O(V), gdzie V jest liczbą wierzchołków grafu.
Zastosowania algorytmów Bellmana Forda:
- Routing sieciowy: Bellman-Ford jest używany w sieciach komputerowych do znajdowania najkrótszych ścieżek w tablicach routingu, pomagając pakietom danych efektywnie poruszać się po sieciach.
- Nawigacja GPS: Urządzenia GPS wykorzystują firmę Bellman-Ford do obliczania najkrótszych i najszybszych tras między lokalizacjami, wspomagając aplikacje i urządzenia nawigacyjne.
- Transport i logistyka: Algorytm Bellmana-Forda można zastosować do wyznaczania optymalnych tras pojazdów w transporcie i logistyce, minimalizując zużycie paliwa i czas podróży.
- Produkcja gier: Bellmana-Forda można wykorzystać do modelowania ruchu i nawigacji w wirtualnych światach podczas tworzenia gier, gdzie różne ścieżki mogą wiązać się z różnymi kosztami i przeszkodami.
- Robotyka i pojazdy autonomiczne: Algorytm pomaga w planowaniu trasy dla robotów lub pojazdów autonomicznych, biorąc pod uwagę przeszkody, ukształtowanie terenu i zużycie energii.
Wady algorytmu Bellmana Forda:
- Algorytm Bellmana-Forda nie powiedzie się, jeśli wykres zawiera cykl zboczy ujemnych.
Powiązane artykuły na temat algorytmów najkrótszej ścieżki z jednego źródła: