logo

TechCodeview

Bellman-Ford-algoritme

Stel je voor dat je een kaart hebt met verschillende steden die met elkaar verbonden zijn door wegen, waarbij elke weg een bepaalde afstand heeft. De Bellman-Ford-algoritme is als een gids die je helpt het kortste pad van de ene stad naar alle andere steden te vinden, zelfs als sommige wegen een negatieve lengte hebben. Het is als een GPS voor computers: handig om uit te zoeken wat de snelste manier is om van het ene punt naar het andere in een netwerk te komen. In dit artikel gaan we dieper in op hoe dit algoritme werkt en waarom het zo handig is bij het oplossen van alledaagse problemen.

Bellman-Ford-algoritme

Inhoudsopgave



Bellman-Ford-algoritme

Bellman-Ford is een enkele bron kortste pad-algoritme dat het kortste pad bepaalt tussen een bepaald bronpunt en elk ander hoekpunt in een grafiek. Dit algoritme kan op beide worden gebruikt gewogen En ongewogen grafieken.

distributieve wet booleaanse algebra

A Bellman-Ford algoritme vindt ook gegarandeerd het kortste pad in een grafiek, vergelijkbaar met Het algoritme van Dijkstra . Hoewel Bellman-Ford langzamer is dan Het algoritme van Dijkstra , het kan grafieken verwerken met negatieve randgewichten , waardoor het veelzijdiger wordt. Het kortste pad kan niet worden gevonden als er een bestaat negatieve cyclus in de grafiek. Als we de negatieve cyclus een oneindig aantal keren blijven doorlopen, zullen de kosten van het pad blijven dalen (ook al neemt de lengte van het pad toe). Als gevolg, Bellman-Ford kan ook detecteren negatieve cycli , wat een belangrijk kenmerk is.

Het idee achter het Bellman Ford-algoritme:

Het belangrijkste principe van het Bellman-Ford-algoritme is dat het begint met een enkele bron en de afstand tot elk knooppunt berekent. De afstand is aanvankelijk onbekend en wordt verondersteld oneindig te zijn, maar naarmate de tijd verstrijkt, versoepelt het algoritme die paden door een paar kortere paden te identificeren. Vandaar dat er wordt gezegd dat Bellman-Ford hierop is gebaseerd Principe van ontspanning .

Principe van ontspanning van de randen voor Bellman-Ford:

  • Er staat dat voor de grafiek N hoekpunten moeten alle randen ontspannen zijn N-1 keer om het kortste pad van de enkele bron te berekenen.
  • Om te detecteren of er al dan niet een negatieve cyclus bestaat, moet je de hele rand nog een keer ontspannen. Als de kortste afstand voor een knooppunt kleiner wordt, kunnen we zeggen dat er een negatieve cyclus bestaat. Kortom als we de randen versoepelen N tijden, en er is enige verandering in de kortste afstand van een knooppunt tussen de N-1e En N-de ontspanning dan bestaat er een negatieve cyclus, anders bestaat er geen.

Waarom het ontspannen van randen N-1 keer ons het kortste pad met één bron oplevert?

In het ergste geval kan er maximaal een kortste pad tussen twee hoekpunten zijn N-1 randen, waar N is het aantal hoekpunten. Dit komt omdat een eenvoudig pad in een grafiek met N hoekpunten kunnen hoogstens bestaan N-1 randen, omdat het onmogelijk is een gesloten lus te vormen zonder een hoekpunt opnieuw te bezoeken.

Door randen te ontspannen N-1 keer zorgt het Bellman-Ford-algoritme ervoor dat de afstandsschattingen voor alle hoekpunten zijn bijgewerkt naar hun optimale waarden, ervan uitgaande dat de grafiek geen cycli met een negatief gewicht bevat die bereikbaar zijn vanaf het bronpunt. Als een grafiek een cyclus met negatief gewicht bevat die bereikbaar is vanaf het bronpunt, kan het algoritme deze daarna detecteren N-1 iteraties, aangezien de negatieve cyclus de kortste padlengten verstoort.

Kortom, ontspannende randjes N-1 times in het Bellman-Ford-algoritme garandeert dat het algoritme alle mogelijke paden met een lengte tot N-1 , wat de maximaal mogelijke lengte is van een kortste pad in een grafiek met N hoekpunten. Hierdoor kan het algoritme de kortste paden van het bronhoekpunt naar alle andere hoekpunten correct berekenen, aangezien er geen cycli met een negatief gewicht zijn.

Waarom duidt de verkleining van de afstand tijdens de zoveelste ontspanning op het bestaan ​​van een negatieve cyclus?

Zoals eerder besproken, is het bereiken van de kortste paden van de enkele bron naar alle andere knooppunten nodig N-1 versoepelingen. Als de N-de relaxatie de kortste afstand voor een knooppunt verder verkleint, impliceert dit dat een bepaalde rand met negatief gewicht opnieuw is overschreden. Het is belangrijk op te merken dat tijdens de N-1 Bij versoepelingen gingen we ervan uit dat elk hoekpunt slechts één keer wordt doorlopen. De verkleining van de afstand tijdens de N-de relaxatie duidt echter op het opnieuw bezoeken van een hoekpunt.

Werking van het Bellman-Ford-algoritme om de negatieve cyclus in de grafiek te detecteren:

Laten we aannemen dat we een grafiek hebben die hieronder wordt weergegeven en we willen met behulp van Bellman-Ford ontdekken of er al dan niet een negatieve cyclus bestaat.

Initiële grafiek

als anders als java

Stap 1: Initialiseer een afstandsarray Dist[] om de kortste afstand voor elk hoekpunt vanaf het bronpunt op te slaan. Aanvankelijk zal de afstand van de bron 0 zijn en de afstand van andere hoekpunten zal INFINITY zijn.

Initialiseer een afstandsarray

Stap 2: Begin met het ontspannen van de randen tijdens de 1e ontspanning:

  • Huidige afstand van B> (afstand van A) + (gewicht van A tot B), d.w.z. oneindig> 0 + 5
    • Daarom is Dist[B] = 5

1e Ontspanning

Stap 3: Tijdens de 2e ontspanning:
  • Huidige afstand van D> (afstand van B) + (gewicht van B tot D), d.w.z. oneindig> 5 + 2
    • Afst[D] = 7
  • Huidige afstand van C> (afstand van B) + (gewicht van B tot C), d.w.z. oneindig> 5 + 1
    • Afst[C] = 6

2e Ontspanning

Stap 4: Tijdens de 3e ontspanning:

  • Huidige afstand van F> (afstand van D) + (gewicht van D tot F), d.w.z. oneindig> 7 + 2
    • Afst[F] = 9
  • Huidige afstand van E> (afstand van C) + (gewicht van C tot E), d.w.z. oneindig> 6 + 1
    • Afst[E] = 7

3e Ontspanning

tekenreeks vergelijken c#

Stap 5: Tijdens de 4e ontspanning:

  • Huidige afstand van D> (afstand van E) + (gewicht van E tot D), d.w.z. 7> 7 + (-1)
    • Afst[D] = 6
  • Huidige afstand van E> (afstand van F) + (gewicht van F tot E), d.w.z. 7> 9 + (-3)
    • Afst[E] = 6

4e Ontspanning

Stap 6: Tijdens de 5e ontspanning:

  • Huidige afstand van F> (afstand van D) + (gewicht van D tot F), d.w.z. 9> 6 + 2
    • Afst[F] = 8
  • Huidige afstand van D> (afstand van E) + (gewicht van E tot D), d.w.z. 6> 6 + (-1)
    • Afst[D] = 5
  • Omdat de grafiek h 6 hoekpunten heeft, had dus tijdens de 5e relaxatie de kortste afstand voor alle hoekpunten moeten worden berekend.

5e Ontspanning

Stap 7: Nu zou de eindrelaxatie, dat wil zeggen de 6e relaxatie, de aanwezigheid van een negatieve cyclus moeten aangeven als er enige veranderingen zijn in de afstandsarray van de 5e relaxatie.

Tijdens de 6e versoepeling zijn de volgende veranderingen te zien:

  • Huidige afstand van E> (afstand van F) + (gewicht van F tot E), d.w.z. 6> 8 + (-3)
    • Afstand[E]=5
  • Huidige afstand van F> (afstand van D) + (gewicht van D tot F), d.w.z. 8> 5 + 2
    • Afstand[F]=7

Omdat we veranderingen in de Distance-array waarnemen, kunnen we concluderen dat er een negatieve cyclus in de grafiek aanwezig is.

6e Ontspanning

Java-tekenreeks bevat

Resultaat: Er bestaat een negatieve cyclus (D->F->E) in de grafiek.

Algoritme om een ​​negatieve cyclus te vinden in een gerichte gewogen grafiek met behulp van Bellman-Ford:

  • Initialiseer afstandsarray dist[] voor elk hoekpunt ' in ' als dist[v] = ONEINDIGHEID .
  • Veronderstel elk hoekpunt (laten we zeggen ‘0’) als bron en wijs dit toe afstand = 0 .
  • Ontspan allemaal randen(u,v,gewicht) N-1 keer volgens de onderstaande voorwaarde:
    • dist[v] = minimum(dist[v], afstand[u] + gewicht)
  • Ontspan nu nog een keer alle randen, d.w.z. de N-de tijd en op basis van de onderstaande twee gevallen kunnen we de negatieve cyclus detecteren:
    • Geval 1 (er bestaat een negatieve cyclus): voor iedereen edge(u, v, gewicht), als dist[u] + gewicht
    • Geval 2 (geen negatieve cyclus): geval 1 faalt voor alle randen.

Omgaan met niet-verbonden grafieken in het algoritme:

Het bovenstaande algoritme en programma werken mogelijk niet als de gegeven grafiek is losgekoppeld. Het werkt wanneer alle hoekpunten bereikbaar zijn vanaf het bronpunt 0 .
Om niet-verbonden grafieken te verwerken, kunnen we het bovenstaande algoritme herhalen voor hoekpunten met afstand = ONEINDIGHEID, of gewoon voor de hoekpunten die niet worden bezocht.

Hieronder vindt u de implementatie van de bovenstaande aanpak:

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->Aantal hoekpunten, E-> Aantal randen int V, E;  // grafiek wordt weergegeven als een reeks randen.  struct Rand* rand; }; // Creëert een grafiek met V-hoekpunten en E-randen struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  grafiek->V = V;  grafiek->E = E;  grafiek->rand = nieuwe Rand[E];  retourgrafiek; } // Een hulpprogrammafunctie die wordt gebruikt om de oplossing af te drukken void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  voor (int i = 0; ik< 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 = grafiek->E;  int dist[V];  // Stap 1: Initialiseer afstanden van src naar alle andere // hoekpunten als ONEINDIG voor (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->rand[j].src;  int v = grafiek->rand[j].dest;  int gewicht = grafiek->rand[j].gewicht;  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->rand[i].src;  int v = grafiek->rand[i].dest;  int gewicht = grafiek->rand[i].gewicht;  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->rand[0].src = 0;  grafiek->rand[0].dest = 1;  grafiek->rand[0].gewicht = -1;  // voeg edge 0-2 toe (of A-C in bovenstaande afbeelding) graph->edge[1].src = 0;  grafiek->rand[1].dest = 2;  grafiek->rand[1].gewicht = 4;  // voeg edge 1-2 toe (of B-C in bovenstaande afbeelding) graph->edge[2].src = 1;  grafiek->rand[2].dest = 2;  grafiek->rand[2].gewicht = 3;  // voeg edge 1-3 toe (of B-D in bovenstaande afbeelding) graph->edge[3].src = 1;  grafiek->rand[3].dest = 3;  grafiek->rand[3].gewicht = 2;  // voeg edge 1-4 toe (of BE in bovenstaande afbeelding) graph->edge[4].src = 1;  grafiek->rand[4].dest = 4;  grafiek->rand[4].gewicht = 2;  // voeg edge 3-2 toe (of D-C in bovenstaande afbeelding) graph->edge[5].src = 3;  grafiek->rand[5].dest = 2;  grafiek->rand[5].gewicht = 5;  // voeg edge 3-1 toe (of D-B in bovenstaande afbeelding) graph->edge[6].src = 3;  grafiek->rand[6].dest = 1;  grafiek->rand[6].gewicht = 1;  // voeg rand 4-3 toe (of E-D in bovenstaande afbeelding) graph->edge[7].src = 4;  grafiek->rand[7].dest = 3;  grafiek->rand[7].gewicht = -3;    // Functieaanroep BellmanFord(grafiek, 0);  retour 0; }>
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);>
Uitvoer 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Complexiteitsanalyse van het Bellman-Ford-algoritme :

  • Tijdcomplexiteit wanneer grafiek is verbonden:
    • Beste geval: O(E), wanneer de afstandsarray na de eerste en tweede relaxatie hetzelfde zijn, kunnen we eenvoudigweg de verdere verwerking stoppen
    • Gemiddeld geval: O(V*E)
    • Het slechtste geval: O(V*E)
  • Tijdcomplexiteit wanneer de grafiek is losgekoppeld :
    • Alle gevallen: O(E*(V^2))
  • Hulpruimte: O(V), waarbij V het aantal hoekpunten in de grafiek is.

Bellman Ford's algoritmetoepassingen:

  • Netwerkroutering: Bellman-Ford wordt gebruikt in computernetwerken om de kortste paden in routeringstabellen te vinden, waardoor datapakketten efficiënt door netwerken kunnen navigeren.
  • GPS-navigatie: GPS-apparaten gebruiken Bellman-Ford om de kortste of snelste routes tussen locaties te berekenen, met behulp van navigatie-apps en -apparaten.
  • Transport en logistiek: Het algoritme van Bellman-Ford kan worden toegepast om de optimale paden voor voertuigen in transport en logistiek te bepalen, waardoor het brandstofverbruik en de reistijd worden geminimaliseerd.
  • Spelontwikkeling: Bellman-Ford kan worden gebruikt om beweging en navigatie binnen virtuele werelden bij de ontwikkeling van games te modelleren, waarbij verschillende paden verschillende kosten of obstakels kunnen hebben.
  • Robotica en autonome voertuigen: Het algoritme helpt bij het plannen van routes voor robots of autonome voertuigen, waarbij rekening wordt gehouden met obstakels, terrein en energieverbruik.

Nadeel van het algoritme van Bellman Ford:

  • Het Bellman-Ford-algoritme mislukt als de grafiek een negatieve flankcyclus bevat.

Gerelateerde artikelen over algoritmen voor het kortste pad uit één bron: