logo

TechCodeview

Bellman-Fordov algoritmus

Predstavte si, že máte mapu s rôznymi mestami prepojenými cestami, pričom každá cesta má určitú vzdialenosť. The Algoritmus Bellman-Ford je ako sprievodca, ktorý vám pomôže nájsť najkratšiu cestu z jedného mesta do všetkých ostatných miest, aj keď niektoré cesty majú zápornú dĺžku. Je to ako a GPS pre počítače, užitočné na nájdenie najrýchlejšieho spôsobu, ako sa dostať z jedného bodu do druhého v sieti. V tomto článku sa bližšie pozrieme na to, ako tento algoritmus funguje a prečo je taký užitočný pri riešení každodenných problémov.

Bellman-Ford-algoritmus

Obsah



Bellman-Fordov algoritmus

Bellman-Ford je a jediný zdroj algoritmus najkratšej cesty, ktorý určuje najkratšiu cestu medzi daným zdrojovým vrcholom a každým iným vrcholom v grafe. Tento algoritmus je možné použiť na oboch vážený a nevážený grafov.

synchronizácia vlákien

A Bellman-Ford algoritmus tiež zaručene nájde najkratšiu cestu v grafe, podobne ako Dijkstrov algoritmus . Hoci Bellman-Ford je pomalší ako Dijkstrov algoritmus , je schopný pracovať s grafmi záporné závažia hrán , čo ho robí všestrannejším. Najkratšiu cestu nemožno nájsť, ak existuje a negatívny cyklus v grafe. Ak budeme pokračovať v obchádzaní negatívneho cyklu nekonečne veľakrát, potom náklady na cestu budú naďalej klesať (aj keď sa dĺžka cesty zvyšuje). Ako výsledok, Bellman-Ford je tiež schopný odhaliť negatívne cykly , čo je dôležitá vlastnosť.

Myšlienka algoritmu Bellmana Forda:

Primárnym princípom Bellman-Fordovho algoritmu je, že začína s jedným zdrojom a vypočítava vzdialenosť ku každému uzlu. Vzdialenosť je spočiatku neznáma a predpokladá sa, že je nekonečná, ale ako čas plynie, algoritmus tieto cesty uvoľňuje identifikáciou niekoľkých kratších ciest. Preto sa hovorí, že Bellman-Ford je založený na Princíp relaxácie .

Princíp uvoľnenia hrán pre Bellman-Ford:

  • Uvádza, že pre graf má N vrcholy, všetky okraje by mali byť uvoľnené N-1 časov na výpočet najkratšej cesty z jedného zdroja.
  • Ak chcete zistiť, či existuje alebo neexistuje negatívny cyklus, uvoľnite celú hranu ešte raz a ak sa najkratšia vzdialenosť pre ktorýkoľvek uzol zníži, môžeme povedať, že existuje negatívny cyklus. Skrátka ak uvoľníme okraje N časy, a tam je akákoľvek zmena v najkratšej vzdialenosti akéhokoľvek uzla medzi N-1st a Nth relaxácia než negatívny cyklus existuje, inak neexistuje.

Prečo nám Relaxing Edges N-1 krát poskytuje najkratšiu cestu z jedného zdroja?

V najhoršom prípade môže mať najkratšia cesta medzi dvoma vrcholmi najviac N-1 hrany, kde N je počet vrcholov. Je to preto, že jednoduchá cesta v grafe s N vrcholy môžu mať max N-1 hrany, pretože nie je možné vytvoriť uzavretú slučku bez opätovného preskúmania vrcholu.

Uvoľnením okrajov N-1 Algoritmus Bellman-Ford zaisťuje, že odhady vzdialeností pre všetky vrcholy boli aktualizované na ich optimálne hodnoty, za predpokladu, že graf neobsahuje žiadne cykly so zápornou váhou dosiahnuteľné zo zdrojového vrcholu. Ak graf obsahuje cyklus zápornej váhy dosiahnuteľný zo zdrojového vrcholu, algoritmus ho dokáže zistiť po N-1 iterácií, keďže negatívny cyklus narúša najkratšie dĺžky ciest.

Stručne povedané, relaxačné okraje N-1 časy v Bellman-Fordovom algoritme zaručuje, že algoritmus preskúmal všetky možné cesty dĺžky až do N-1 , čo je maximálna možná dĺžka najkratšej cesty v grafe s N vrcholy. To umožňuje algoritmu správne vypočítať najkratšie cesty zo zdrojového vrcholu do všetkých ostatných vrcholov za predpokladu, že neexistujú žiadne cykly so zápornou váhou.

čo znamená xdxd

Prečo zníženie vzdialenosti v N'-tej relaxácii naznačuje existenciu negatívneho cyklu?

Ako už bolo uvedené, dosiahnutie najkratších ciest z jedného zdroja do všetkých ostatných uzlov si vyžaduje N-1 relaxácie. Ak N'-tá relaxácia ďalej znižuje najkratšiu vzdialenosť pre ktorýkoľvek uzol, znamená to, že určitá hrana so zápornou váhou bola ešte raz prekročená. Je dôležité poznamenať, že počas N-1 relaxácií, predpokladali sme, že každý vrchol sa prejde iba raz. Zníženie vzdialenosti počas N'-tej relaxácie však naznačuje opätovnú návštevu vrcholu.

Fungovanie Bellman-Fordovho algoritmu na detekciu negatívneho cyklu v grafe:

Predpokladajme, že máme graf, ktorý je uvedený nižšie, a chceme zistiť, či existuje negatívny cyklus alebo nie pomocou Bellman-Ford.

Počiatočný graf

Krok 1: Inicializujte pole vzdialeností Dist[] na uloženie najkratšej vzdialenosti pre každý vrchol od zdrojového vrcholu. Na začiatku bude vzdialenosť zdroja 0 a vzdialenosť ostatných vrcholov bude NEKONEČNO.

Inicializujte pole vzdialenosti

Krok 2: Začnite uvoľňovať okraje počas 1. relaxácie:

  • Aktuálna vzdialenosť B> (vzdialenosť A) + (hmotnosť A po B) t.j. nekonečno> 0 + 5
    • Preto Dist[B] = 5

1. Relaxácia

Krok 3: Počas 2. relaxácie:
  • Aktuálna vzdialenosť D> (vzdialenosť B) + (hmotnosť B až D) t.j. nekonečno> 5 + 2
    • Vzdialenosť[D] = 7
  • Aktuálna vzdialenosť C> (vzdialenosť B) + (hmotnosť B až C) t.j. nekonečno> 5 + 1
    • Vzdialenosť [C] = 6

2. Relaxácia

Krok 4: Počas 3. relaxácie:

reakčná mapa
  • Aktuálna vzdialenosť F> (Vzdialenosť D ) + (Hmotnosť D až F) t.j. nekonečno> 7 + 2
    • Vzdialenosť[F] = 9
  • Aktuálna vzdialenosť E> (vzdialenosť C ) + (hmotnosť C k E) t.j. nekonečno> 6 + 1
    • Vzdialenosť[E] = 7

3. Relaxácia

Krok 5: Počas 4. relaxácie:

  • Aktuálna vzdialenosť D> (vzdialenosť E) + (hmotnosť E k D) t.j. 7> 7 + (-1)
    • Vzdialenosť[D] = 6
  • Aktuálna vzdialenosť E> (Vzdialenosť F ) + (Hmotnosť F až E) t.j. 7> 9 + (-3)
    • Vzdialenosť[E] = 6

4. Relaxácia

Krok 6: Počas piatej relaxácie:

  • Aktuálna vzdialenosť F> (vzdialenosť D) + (hmotnosť D až F) t.j. 9> 6 + 2
    • Vzdialenosť [F] = 8
  • Aktuálna vzdialenosť D> (vzdialenosť E ) + (hmotnosť E k D) t.j. 6> 6 + (-1)
    • Vzdialenosť[D] = 5
  • Keďže graf h 6 vrcholov, tak počas 5. relaxácie mala byť vypočítaná najkratšia vzdialenosť pre všetky vrcholy.

5. Relaxácia

Krok 7: Teraz posledná relaxácia, t. j. 6. relaxácia, by mala indikovať prítomnosť negatívneho cyklu, ak nastanú nejaké zmeny v poli vzdialeností 5. relaxácie.

Počas 6. relaxácie možno pozorovať tieto zmeny:

  • Aktuálna vzdialenosť E> (Vzdialenosť F) + (Hmotnosť F až E) t.j. 6> 8 + (-3)
    • Vzdialenosť[E]=5
  • Aktuálna vzdialenosť F> (Vzdialenosť D ) + (Hmotnosť D až F) t.j. 8> 5 + 2
    • Vzdial.[F]=7

Keďže pozorujeme zmeny v poli Distance, môžeme dospieť k záveru o prítomnosti negatívneho cyklu v grafe.

6. Relaxácia

Greatandhra

výsledok: V grafe existuje negatívny cyklus (D->F->E).

Algoritmus na nájdenie negatívneho cyklu v riadenom váženom grafe pomocou Bellman-Ford:

  • Inicializujte vzdialenosť poľa dist[] pre každý vrchol ‘ v „ako dist[v] = NEKONEČNO .
  • Predpokladajme akýkoľvek vrchol (povedzme „0“) ako zdroj a priraďte ho vzdialenost = 0 .
  • Uvoľnite sa všetky hrany(u,v,hmotnosť) N-1 časy podľa nižšie uvedenej podmienky:
    • vzdialenosť[v] = minimum (vzdialenosť[v], vzdialenosť[u] + hmotnosť)
  • Teraz uvoľnite všetky okraje ešte raz, tj Nth čas a na základe dvoch nižšie uvedených prípadov môžeme zistiť negatívny cyklus:
    • Prípad 1 (existuje negatívny cyklus): Pre ľubovoľné hrana(u, v, hmotnosť), ak dist[u] + hmotnosť
    • Prípad 2 (žiadny negatívny cyklus): prípad 1 zlyhá pre všetky hrany.

Spracovanie odpojených grafov v algoritme:

Vyššie uvedený algoritmus a program nemusia fungovať, ak je daný graf odpojený. Funguje, keď sú všetky vrcholy dosiahnuteľné zo zdrojového vrcholu 0 .
Aby sme zvládli nespojené grafy, môžeme zopakovať vyššie uvedený algoritmus pre vrcholy, ktoré majú vzdialenosť = NEKONEČNO, alebo jednoducho pre vrcholy, ktoré nie sú navštívené.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

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->Počet vrcholov, E-> Počet hrán int V, E;  // graf je reprezentovaný ako pole hrán.  struct Hrana* hrana; }; // Vytvorí graf s V vrcholmi a E hranami struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graf->V = V;  graf->E = E;  graf->hrana = new Hrana[E];  návratový graf; } // Pomocná funkcia používaná na vytlačenie riešenia void printArr(int dist[], int n) { printf('Vzdialenosť vrcholu od zdroja
');  pre (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 = graf->E;  int dist[V];  // Krok 1: Inicializujte vzdialenosti od src ku všetkým ostatným // vrcholom ako INFINITE for (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->hrana[j].src;  int v = graf->hrana[j].dest;  int vaha = graf->hrana[j].váha;  if (vzdial[u] != INT_MAX && vzdial[u] + hmotnosť< 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->okraj[i].src;  int v = graf->hrana[i].dest;  int vaha = graf->hrana[i].váha;  if (dist[u] != INT_MAX && dist[u] + hmotnosť< 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->hrana[0].src = 0;  graf->hrana[0].dest = 1;  graf->hrana[0].váha = -1;  // pridanie hrany 0-2 (alebo A-C na obrázku vyššie) graph->edge[1].src = 0;  graf->hrana[1].dest = 2;  graf->hrana[1].váha = 4;  // pridanie hrany 1-2 (alebo B-C na obrázku vyššie) graph->edge[2].src = 1;  graf->hrana[2].dest = 2;  graf->hrana[2].váha = 3;  // pridanie hrany 1-3 (alebo B-D na obrázku vyššie) graph->edge[3].src = 1;  graf->hrana[3].dest = 3;  graf->hrana[3].váha = 2;  // pridanie hrany 1-4 (alebo B-E na obrázku vyššie) graph->edge[4].src = 1;  graf->hrana[4].dest = 4;  graf->hrana[4].váha = 2;  // pridanie hrany 3-2 (alebo D-C na obrázku vyššie) graph->edge[5].src = 3;  graf->hrana[5].dest = 2;  graf->hrana[5].váha = 5;  // pridanie hrany 3-1 (alebo D-B na obrázku vyššie) graph->edge[6].src = 3;  graf->hrana[6].dest = 1;  graf->hrana[6].váha = 1;  // pridanie hrany 4-3 (alebo E-D na obrázku vyššie) graph->edge[7].src = 4;  graf->hrana[7].dest = 3;  graf->hrana[7].váha = -3;    // Volanie funkcie BellmanFord(graph, 0);  návrat 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);>
Výkon 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Analýza zložitosti Bellman-Fordovho algoritmu :

  • Časová zložitosť pri prepojení grafu:
    • Najlepší prípad: O(E), keď je pole vzdialeností po 1. a 2. relaxácii rovnaké, môžeme jednoducho zastaviť ďalšie spracovanie
    • Priemerný prípad: O(V*E)
    • V najhoršom prípade: O(V*E)
  • Časová zložitosť, keď je graf odpojený :
    • Všetky prípady: O(E*(V^2))
  • Pomocný priestor: O(V), kde V je počet vrcholov v grafe.

Aplikácie algoritmov Bellmana Forda:

  • Smerovanie siete: Bellman-Ford sa používa v počítačových sieťach na nájdenie najkratších ciest v smerovacích tabuľkách, čím pomáha dátovým paketom efektívne prechádzať sieťami.
  • Navigácia GPS: Zariadenia GPS používajú Bellman-Ford na výpočet najkratších alebo najrýchlejších trás medzi miestami, čím pomáhajú navigačným aplikáciám a zariadeniam.
  • Doprava a logistika: Algoritmus Bellman-Ford možno použiť na určenie optimálnych trás pre vozidlá v doprave a logistike, čím sa minimalizuje spotreba paliva a čas jazdy.
  • Vývoj hry: Bellman-Ford možno použiť na modelovanie pohybu a navigácie vo virtuálnych svetoch pri vývoji hier, kde rôzne cesty môžu mať rôzne náklady alebo prekážky.
  • Robotika a autonómne vozidlá: Algoritmus pomáha pri plánovaní cesty pre roboty alebo autonómne vozidlá, berúc do úvahy prekážky, terén a spotrebu energie.

Nevýhoda algoritmu Bellmana Forda:

  • Algoritmus Bellman-Ford zlyhá, ak graf obsahuje akýkoľvek cyklus zápornej hrany.

Súvisiace články o algoritmoch najkratšej cesty s jedným zdrojom: