logo

TechCodeview

Bellman-Ford-Algorithmus

Stellen Sie sich vor, Sie haben eine Karte mit verschiedenen Städten, die durch Straßen verbunden sind, wobei jede Straße eine bestimmte Entfernung hat. Der Bellman-Ford-Algorithmus ist wie ein Reiseführer, der Ihnen hilft, den kürzesten Weg von einer Stadt zu allen anderen Städten zu finden, auch wenn einige Straßen negative Längen haben. Es ist wie ein GPS für Computer, nützlich, um herauszufinden, wie man in einem Netzwerk am schnellsten von einem Punkt zum anderen gelangt. In diesem Artikel werfen wir einen genaueren Blick darauf, wie dieser Algorithmus funktioniert und warum er bei der Lösung alltäglicher Probleme so praktisch ist.

Bellman-Ford-Algorithmus

Inhaltsverzeichnis



Bellman-Ford-Algorithmus

Bellman-Ford ist ein einzige Quelle Algorithmus für den kürzesten Pfad, der den kürzesten Pfad zwischen einem bestimmten Quellscheitelpunkt und jedem anderen Scheitelpunkt in einem Diagramm bestimmt. Dieser Algorithmus kann für beide verwendet werden gewichtet Und ungewichtet Grafiken.

Java Mathe.min

A Bellman-Ford Der Algorithmus findet auch garantiert den kürzesten Weg in einem Diagramm, ähnlich wie Dijkstras Algorithmus . Obwohl Bellman-Ford langsamer ist als Dijkstras Algorithmus , ist es in der Lage, Diagramme mit zu verarbeiten negative Kantengewichte , was es vielseitiger macht. Der kürzeste Weg kann nicht gefunden werden, wenn ein vorhanden ist negativer Kreislauf in der Grafik. Wenn wir den negativen Kreislauf weiterhin unendlich oft durchlaufen, werden die Kosten des Pfades weiter sinken (auch wenn die Länge des Pfades zunimmt). Infolge, Bellman-Ford ist auch in der Lage zu erkennen negative Zyklen , was eine wichtige Funktion ist.

Die Idee hinter dem Bellman-Ford-Algorithmus:

Das Hauptprinzip des Bellman-Ford-Algorithmus besteht darin, dass er mit einer einzigen Quelle beginnt und die Entfernung zu jedem Knoten berechnet. Der Abstand ist zunächst unbekannt und wird als unendlich angenommen, aber im Laufe der Zeit entspannt der Algorithmus diese Pfade, indem er einige kürzere Pfade identifiziert. Daher wird gesagt, dass Bellman-Ford darauf basiert Prinzip der Entspannung .

Prinzip der Kantenrelaxation nach Bellman-Ford:

  • Es besagt, dass für den Graphen Folgendes gilt: N Scheitelpunkte, alle Kanten sollten entspannt sein N-1 mal, um den kürzesten Weg aus einer einzigen Quelle zu berechnen.
  • Um festzustellen, ob ein negativer Zyklus existiert oder nicht, entspannen Sie die gesamte Kante noch einmal. Wenn sich der kürzeste Abstand für einen Knoten verringert, können wir sagen, dass ein negativer Zyklus existiert. Kurz gesagt, wenn wir die Kanten entspannen N Zeiten, und es gibt jede Änderung in der kürzesten Entfernung eines Knotens zwischen den N-1 Und Nth Entspannung als ein negativer Zyklus existiert, andernfalls existiert er nicht.

Warum gibt uns die N-1-fache Entspannung der Kanten den kürzesten Weg aus einer einzigen Quelle?

Im schlimmsten Fall kann es höchstens einen kürzesten Weg zwischen zwei Knoten geben N-1 Kanten, wo N ist die Anzahl der Eckpunkte. Dies liegt daran, dass ein einfacher Pfad in einem Diagramm mit N Scheitelpunkte können höchstens haben N-1 Kanten, da es unmöglich ist, eine geschlossene Schleife zu bilden, ohne einen Scheitelpunkt erneut zu besuchen.

Durch entspannende Kanten N-1 Mal stellt der Bellman-Ford-Algorithmus sicher, dass die Entfernungsschätzungen für alle Scheitelpunkte auf ihre optimalen Werte aktualisiert wurden, vorausgesetzt, das Diagramm enthält keine Zyklen mit negativem Gewicht, die vom Quellscheitelpunkt aus erreichbar sind. Wenn ein Graph einen Zyklus mit negativem Gewicht enthält, der vom Quellscheitelpunkt aus erreichbar ist, kann der Algorithmus ihn anschließend erkennen N-1 Iterationen, da der negative Zyklus die kürzesten Pfadlängen unterbricht.

Zusammenfassend: entspannende Kanten N-1 Zeiten im Bellman-Ford-Algorithmus garantiert, dass der Algorithmus alle möglichen Pfade mit einer Länge von bis zu untersucht hat N-1 , das ist die maximal mögliche Länge eines kürzesten Pfades in einem Diagramm mit N Eckpunkte. Dadurch kann der Algorithmus die kürzesten Pfade vom Quellscheitelpunkt zu allen anderen Scheitelpunkten korrekt berechnen, vorausgesetzt, es gibt keine Zyklen mit negativem Gewicht.

Warum weist die Verringerung der Distanz in der N-ten Entspannung auf die Existenz eines negativen Zyklus hin?

Wie bereits erwähnt, erfordert das Erreichen kürzester Pfade aus einer einzigen Quelle zu allen anderen Knoten N-1 Entspannungen. Wenn die N-te Entspannung den kürzesten Abstand für einen beliebigen Knoten weiter verringert, bedeutet dies, dass eine bestimmte Kante mit negativem Gewicht erneut durchlaufen wurde. Es ist wichtig zu beachten, dass während der N-1 Bei den Entspannungen haben wir angenommen, dass jeder Knoten nur einmal durchlaufen wird. Die Verringerung des Abstands während der N-ten Relaxation deutet jedoch darauf hin, dass ein Scheitelpunkt erneut besucht wird.

Funktionsweise des Bellman-Ford-Algorithmus zur Erkennung des negativen Zyklus im Diagramm:

Nehmen wir an, wir haben ein Diagramm, das unten dargestellt ist, und wir möchten mithilfe von Bellman-Ford herausfinden, ob es einen negativen Zyklus gibt oder nicht.

Erstes Diagramm

Schritt 1: Initialisieren Sie ein Distanzarray Dist[], um für jeden Scheitelpunkt den kürzesten Abstand vom Quellscheitelpunkt zu speichern. Anfänglich beträgt der Abstand der Quelle 0 und der Abstand anderer Scheitelpunkte UNENDLICH.

bestes Lächeln der Welt

Initialisieren Sie ein Distanzarray

Schritt 2: Beginnen Sie mit der Entspannung der Kanten während der 1. Entspannung:

  • Aktueller Abstand von B> (Abstand von A) + (Gewicht von A zu B), d. h. Unendlich> 0 + 5
    • Daher ist Dist[B] = 5

1. Entspannung

Schritt 3: Während der 2. Entspannung:
  • Aktueller Abstand von D> (Abstand von B) + (Gewicht von B zu D), d. h. Unendlich> 5 + 2
    • Dist[D] = 7
  • Aktueller Abstand von C> (Abstand von B) + (Gewicht von B zu C), d. h. Unendlich> 5 + 1
    • Dist[C] = 6

2. Entspannung

C-Programm zum String-Vergleich

Schritt 4: Während der 3. Entspannung:

  • Aktueller Abstand von F> (Abstand von D) + (Gewicht von D zu F), d. h. Unendlich> 7 + 2
    • Dist[F] = 9
  • Aktueller Abstand von E> (Abstand von C) + (Gewicht von C zu E), d. h. Unendlich> 6 + 1
    • Dist[E] = 7

3. Entspannung

Schritt 5: Während der 4. Entspannung:

  • Aktueller Abstand von D> (Abstand von E) + (Gewicht von E zu D), d. h. 7> 7 + (-1)
    • Dist[D] = 6
  • Aktueller Abstand von E> (Abstand von F) + (Gewicht von F zu E), d. h. 7> 9 + (-3)
    • Dist[E] = 6

4. Entspannung

Schritt 6: Während der 5. Entspannung:

  • Aktueller Abstand von F> (Abstand von D) + (Gewicht von D zu F), d. h. 9> 6 + 2
    • Dist[F] = 8
  • Aktueller Abstand von D> (Abstand von E) + (Gewicht von E zu D), d. h. 6> 6 + (-1)
    • Dist[D] = 5
  • Da der Graph 6 Eckpunkte hat, hätte bei der 5. Entspannung der kürzeste Abstand für alle Eckpunkte berechnet werden sollen.

5. Entspannung

Schritt 7: Nun sollte die endgültige Entspannung, d. h. die 6. Entspannung, das Vorhandensein eines negativen Zyklus anzeigen, wenn es irgendwelche Änderungen im Abstandsbereich der 5. Entspannung gibt.

Während der 6. Lockerung sind folgende Veränderungen zu erkennen:

  • Aktueller Abstand von E> (Abstand von F) + (Gewicht von F zu E), d. h. 6> 8 + (-3)
    • Dist[E]=5
  • Aktueller Abstand von F> (Abstand von D) + (Gewicht von D zu F), d. h. 8> 5 + 2
    • Dist[F]=7

Da wir Änderungen im Abstandsarray beobachten, können wir auf das Vorhandensein eines negativen Zyklus im Diagramm schließen.

6. Entspannung

PD-Zusammenführung

Ergebnis: Im Diagramm existiert ein negativer Zyklus (D->F->E).

Algorithmus zum Finden eines negativen Zyklus in einem gerichteten gewichteten Diagramm mithilfe von Bellman-Ford:

  • Distanzarray dist[] für jeden Scheitelpunkt initialisieren In ' als dist[v] = UNENDLICH .
  • Nehmen Sie einen beliebigen Scheitelpunkt (sagen wir „0“) als Quelle an und weisen Sie ihn zu dist = 0 .
  • Entspannen Sie sich Kanten(u,v,Gewicht) N-1 Mal gemäß der folgenden Bedingung:
    • dist[v] = Minimum(dist[v], distance[u] + Gewicht)
  • Entspannen Sie nun noch einmal alle Kanten, d. h. die Nth Zeit und basierend auf den beiden folgenden Fällen können wir den negativen Zyklus erkennen:
    • Fall 1 (negativer Zyklus vorhanden): Für jeden Kante(u, v, Gewicht), wenn dist[u] + Gewicht
    • Fall 2 (Kein negativer Zyklus): Fall 1 schlägt für alle Kanten fehl.

Umgang mit nicht zusammenhängenden Diagrammen im Algorithmus:

Der obige Algorithmus und das obige Programm funktionieren möglicherweise nicht, wenn das angegebene Diagramm nicht verbunden ist. Es funktioniert, wenn alle Scheitelpunkte vom Quellscheitelpunkt aus erreichbar sind 0 .
Um nicht zusammenhängende Diagramme zu verarbeiten, können wir den obigen Algorithmus für Knoten mit Knoten wiederholen Entfernung = UNENDLICH, oder einfach für die Eckpunkte, die nicht besucht werden.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

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->Anzahl der Eckpunkte, E-> Anzahl der Kanten int V, E;  // Graph wird als Array von Kanten dargestellt.  struct Edge* edge; }; // Erstellt einen Graphen mit V Eckpunkten und E Kanten struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graph->V = V;  graph->E = E;  graph->edge = new Edge[E];  Rückgabediagramm; } // Eine Dienstprogrammfunktion zum Drucken der Lösung void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  für (int i = 0; i< 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 = graph->E;  int dist[V];  // Schritt 1: Abstände von src zu allen anderen // Eckpunkten als UNENDLICH initialisieren für (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->Kante[j].src;  int v = graph->edge[j].dest;  intweight = graph->edge[j].weight;  if (dist[u] != INT_MAX && dist[u] + Gewicht< 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->Kante[i].src;  int v = graph->edge[i].dest;  intweight = graph->edge[i].weight;  if (dist[u] != INT_MAX && dist[u] + Gewicht< 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->Kante[0].src = 0;  graph->edge[0].dest = 1;  graph->edge[0].weight = -1;  // Kante 0-2 (oder A-C in der obigen Abbildung) hinzufügen graph->edge[1].src = 0;  graph->edge[1].dest = 2;  graph->edge[1].weight = 4;  // Kante 1-2 (oder B-C in der obigen Abbildung) hinzufügen graph->edge[2].src = 1;  graph->edge[2].dest = 2;  graph->edge[2].weight = 3;  // Kante 1-3 (oder B-D in der obigen Abbildung) hinzufügen graph->edge[3].src = 1;  graph->edge[3].dest = 3;  graph->edge[3].weight = 2;  // Kante 1-4 (oder B-E in der obigen Abbildung) hinzufügen graph->edge[4].src = 1;  graph->edge[4].dest = 4;  graph->edge[4].weight = 2;  // Kante 3-2 (oder D-C in der obigen Abbildung) hinzufügen graph->edge[5].src = 3;  graph->edge[5].dest = 2;  graph->edge[5].weight = 5;  // Kante 3-1 (oder D-B in der obigen Abbildung) hinzufügen graph->edge[6].src = 3;  graph->edge[6].dest = 1;  graph->edge[6].weight = 1;  // Kante 4-3 (oder E-D in der obigen Abbildung) hinzufügen graph->edge[7].src = 4;  graph->edge[7].dest = 3;  graph->edge[7].weight = -3;    // Funktionsaufruf BellmanFord(graph, 0);  0 zurückgeben; }>
Java 
// 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);>
Ausgabe 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Komplexitätsanalyse des Bellman-Ford-Algorithmus :

  • Zeitkomplexität, wenn der Graph verbunden ist:
    • I'm besten fall: O(E), wenn die Distanzarrays nach der 1. und 2. Relaxation gleich sind, können wir die weitere Verarbeitung einfach stoppen
    • Durchschnittlicher Fall: O(V*E)
    • Schlimmsten Fall: O(V*E)
  • Zeitkomplexität, wenn der Graph nicht verbunden ist :
    • Alle Fälle: O(E*(V^2))
  • Hilfsraum: O(V), wobei V die Anzahl der Eckpunkte im Diagramm ist.

Anwendungen des Algorithmus von Bellman Ford:

  • Netzwerkrouting: Bellman-Ford wird in Computernetzwerken verwendet, um die kürzesten Pfade in Routing-Tabellen zu finden und so Datenpaketen bei der effizienten Navigation durch Netzwerke zu helfen.
  • GPS-Navigation: GPS-Geräte verwenden Bellman-Ford, um die kürzesten oder schnellsten Routen zwischen Standorten zu berechnen und unterstützen so Navigations-Apps und -Geräte.
  • Transport und Logistik: Der Bellman-Ford-Algorithmus kann angewendet werden, um die optimalen Wege für Fahrzeuge in Transport und Logistik zu bestimmen und so den Kraftstoffverbrauch und die Reisezeit zu minimieren.
  • Spieleentwicklung: Bellman-Ford kann zur Modellierung von Bewegung und Navigation in virtuellen Welten in der Spieleentwicklung verwendet werden, in denen unterschiedliche Wege unterschiedliche Kosten oder Hindernisse mit sich bringen können.
  • Robotik und autonome Fahrzeuge: Der Algorithmus hilft bei der Wegplanung für Roboter oder autonome Fahrzeuge unter Berücksichtigung von Hindernissen, Gelände und Energieverbrauch.

Nachteil des Bellman-Ford-Algorithmus:

  • Der Bellman-Ford-Algorithmus schlägt fehl, wenn der Graph einen negativen Kantenzyklus enthält.

Verwandte Artikel zu Single-Source-Shortest-Path-Algorithmen: