logo

TechCodeview

Bellman-Ford algoritmas

Įsivaizduokite, kad turite žemėlapį su skirtingais miestais, sujungtais keliais, kurių kiekvienas turi tam tikrą atstumą. The Bellman-Ford algoritmas yra tarsi vadovas, padedantis rasti trumpiausią kelią iš vieno miesto į visus kitus miestus, net jei kai kurių kelių ilgis yra neigiamas. Tai kaip a GPS kompiuteriams, naudinga norint išsiaiškinti, kaip greičiausias būdas patekti iš vieno taško į kitą tinkle. Šiame straipsnyje mes atidžiau pažvelgsime į tai, kaip šis algoritmas veikia ir kodėl jis toks patogus sprendžiant kasdienes problemas.

Bellman-Ford-Algoritmas

Turinys



Bellman-Ford algoritmas

Bellman-Ford yra vienas šaltinis trumpiausio kelio algoritmas, kuris nustato trumpiausią kelią tarp nurodytos šaltinio viršūnės ir kiekvienos kitos grafo viršūnės. Šis algoritmas gali būti naudojamas abiem atvejais svertinis ir nesvertas grafikai.

daliniai latekso dariniai

A Bellman-Ford algoritmas taip pat garantuoja trumpiausią kelią grafike, panašų į Dijkstros algoritmas . Nors Bellman-Ford yra lėtesnis nei Dijkstros algoritmas , jis gali tvarkyti grafikus su neigiamų briaunų svarmenys , todėl jis yra universalesnis. Neįmanoma rasti trumpiausio kelio, jei yra a neigiamas ciklas grafike. Jei ir toliau apeisime neigiamą ciklą be galo daug kartų, tada kelio kaina ir toliau mažės (nors kelio ilgis didėja). Kaip rezultatas, Bellman-Ford taip pat gali aptikti neigiami ciklai , kuri yra svarbi savybė.

„Bellman Ford“ algoritmo idėja:

Pagrindinis Bellman-Ford algoritmo principas yra tas, kad jis prasideda nuo vieno šaltinio ir apskaičiuoja atstumą iki kiekvieno mazgo. Iš pradžių atstumas nežinomas ir manoma, kad jis yra begalinis, tačiau laikui bėgant algoritmas atpalaiduoja tuos kelius, nustatydamas kelis trumpesnius kelius. Taigi sakoma, kad Bellman-Ford yra pagrįstas Atsipalaidavimo principas .

„Bellman-Ford“ briaunų atpalaidavimo principas:

  • Jame teigiama, kad grafui, turinčiam N viršūnių, visi kraštai turi būti atpalaiduoti N-1 kartų, kad apskaičiuotų vieno šaltinio trumpiausią kelią.
  • Norėdami nustatyti, ar yra neigiamas ciklas, ar ne, atpalaiduokite visą kraštą dar kartą ir, jei trumpiausias atstumas bet kuriam mazgui sumažėja, galime sakyti, kad egzistuoja neigiamas ciklas. Trumpai tariant, jei atpalaiduojame kraštus N kartų, ir pasikeičia trumpiausias bet kurio mazgo atstumas tarp N-1st ir Nth atsipalaidavimas nei neigiamas ciklas egzistuoja, kitaip neegzistuoja.

Kodėl „Relaxing Edges“ N-1 kartą suteikia trumpiausią kelią iš vieno šaltinio?

Blogiausiu atveju gali būti trumpiausias kelias tarp dviejų viršūnių N-1 kraštai, kur N yra viršūnių skaičius. Taip yra todėl, kad paprastas kelias grafike su N viršūnės gali turėti daugiausia N-1 briaunas, nes neįmanoma sudaryti uždaro ciklo neperžiūrėjus viršūnės.

Atpalaiduojant kraštus N-1 kartų, Bellman-Ford algoritmas užtikrina, kad visų viršūnių atstumo įverčiai būtų atnaujinti iki jų optimalių verčių, darant prielaidą, kad grafike nėra jokių neigiamo svorio ciklų, pasiekiamų iš šaltinio viršūnės. Jei grafike yra neigiamo svorio ciklas, pasiekiamas iš šaltinio viršūnės, algoritmas gali aptikti jį po N-1 iteracijos, nes neigiamas ciklas sutrikdo trumpiausius kelio ilgius.

base64 javascript dekodavimas

Apibendrinant, atpalaiduoja kraštai N-1 kartų Bellman-Ford algoritmas garantuoja, kad algoritmas ištyrė visus galimus ilgio kelius iki N-1 , kuris yra didžiausias galimas trumpiausio kelio ilgis grafike su N viršūnių. Tai leidžia algoritmui teisingai apskaičiuoti trumpiausius kelius nuo šaltinio viršūnės iki visų kitų viršūnių, atsižvelgiant į tai, kad nėra neigiamo svorio ciklų.

Kodėl atstumo sumažinimas N-ojo atsipalaidavimo metu rodo, kad yra neigiamas ciklas?

Kaip aptarta anksčiau, pasiekti trumpiausius kelius iki visų kitų mazgų reikia vieno šaltinio N-1 atsipalaidavimus. Jei N-asis atsipalaidavimas dar labiau sumažina trumpiausią bet kurio mazgo atstumą, tai reiškia, kad tam tikras kraštas su neigiamu svoriu buvo kirtas dar kartą. Svarbu pažymėti, kad per N-1 relaksacijas, manėme, kad kiekviena viršūnė įveikiama tik vieną kartą. Tačiau atstumo sumažėjimas N-ojo atsipalaidavimo metu rodo, kad reikia pakartotinai apsilankyti viršūnėje.

Bellman-Ford algoritmo veikimas, norint aptikti neigiamą ciklą diagramoje:

Tarkime, kad turime žemiau pateiktą grafiką ir norime sužinoti, ar yra neigiamas ciklas, ar nenaudojame Bellman-Ford.

Pradinis grafikas

1 žingsnis: Inicijuokite atstumo masyvą Dist[], kad išsaugotumėte trumpiausią kiekvienos viršūnės atstumą nuo šaltinio viršūnės. Iš pradžių šaltinio atstumas bus 0, o kitų viršūnių atstumas bus BEGALIS.

Inicijuoti atstumo masyvą

2 žingsnis: Pradėkite atpalaiduoti kraštus 1-ojo atsipalaidavimo metu:

  • Srovės atstumas B> (atstumas nuo A) + (nuo A iki B svoris), t. y. begalybė> 0 + 5
    • Todėl Dist[B] = 5

1-asis atsipalaidavimas

3 veiksmas: Antrojo atsipalaidavimo metu:
  • Dabartinis atstumas nuo D> (atstumas nuo B) + (nuo B iki D svoris), t. y. begalybė> 5 + 2
    • Dist[D] = 7
  • Srovės atstumas C> (atstumas nuo B) + (nuo B iki C svoris), t. y. begalybė> 5 + 1
    • Dist[C] = 6

2-asis atsipalaidavimas

4 veiksmas: Trečiojo atsipalaidavimo metu:

  • Srovės atstumas F> (atstumas nuo D ) + (nuo D iki F svoris), t. y. begalybė> 7 + 2
    • Dist[F] = 9
  • Srovės atstumas E> (atstumas C ) + (nuo C iki E svoris), t. y. begalybė> 6 + 1
    • Dist[E] = 7

3 atsipalaidavimas

5 veiksmas: 4-ojo atsipalaidavimo metu:

stygų metodai java
  • Dabartinis atstumas nuo D> (atstumas nuo E) + (nuo E iki D svoris), t. y. 7> 7 + (-1)
    • Dist[D] = 6
  • Dabartinis atstumas E> (atstumas nuo F ) + (nuo F iki E svoris), t. y. 7> 9 + (-3)
    • Dist[E] = 6

4-asis atsipalaidavimas

6 veiksmas: 5-ojo atsipalaidavimo metu:

  • Dabartinis atstumas nuo F> (atstumas nuo D) + (nuo D iki F svoris), t. y. 9> 6 + 2
    • Dist[F] = 8
  • Dabartinis atstumas nuo D> (atstumas nuo E ) + (nuo E iki D svoris), t. y. 6> 6 + (-1)
    • Dist[D] = 5
  • Kadangi grafas h 6 viršūnes, Taigi per 5 relaksaciją turėjo būti apskaičiuotas trumpiausias atstumas visoms viršūnėms.

5 atsipalaidavimas

7 veiksmas: Dabar galutinis atsipalaidavimas, ty 6-asis atsipalaidavimas, turėtų rodyti neigiamą ciklą, jei yra kokių nors pokyčių 5-ojo atsipalaidavimo atstumo matricoje.

6-ojo atsipalaidavimo metu galima pastebėti šiuos pokyčius:

  • Dabartinis atstumas E> (atstumas nuo F) + (nuo F iki E svoris), t. y. 6> 8 + (-3)
    • Dist[E]=5
  • Dabartinis atstumas nuo F> (atstumas nuo D ) + (nuo D iki F svoris), t. y. 8> 5 + 2
    • Dist[F]=7

Kadangi mes stebime pokyčius atstumo masyve, galime daryti išvadą, kad grafike yra neigiamas ciklas.

6-asis atsipalaidavimas

Greatandhra

Rezultatas: Grafike yra neigiamas ciklas (D->F->E).

Algoritmas, kaip rasti neigiamą ciklą nukreiptoje svertinėje diagramoje naudojant Bellman-Ford:

  • Inicijuoti atstumo masyvo dist[] kiekvienai viršūnei ' in ‘ kaip dist[v] = BEGALIS .
  • Priimkite bet kurią viršūnę (tarkime „0“) kaip šaltinį ir priskirkite dist = 0 .
  • Atsipalaiduokite visi briaunos(u,v,svoris) N-1 kartus pagal toliau nurodytą sąlygą:
    • distancija [v] = minimumas (atstumas [v], atstumas [u] + svoris)
  • Dabar dar kartą atpalaiduokite visus kraštus, t. y Nth laiko ir remdamiesi toliau nurodytais dviem atvejais galime aptikti neigiamą ciklą:
    • 1 atvejis (yra neigiamas ciklas): bet kuriam briauna(u, v, svoris), jei dist[u] + svoris
    • 2 atvejis (nėra neigiamo ciklo): 1 atvejis nepavyksta visuose kraštuose.

Atjungtų grafikų tvarkymas algoritme:

Aukščiau pateiktas algoritmas ir programa gali neveikti, jei nurodytas grafikas yra atjungtas. Jis veikia, kai visos viršūnės pasiekiamos iš šaltinio viršūnės 0 .
Norėdami apdoroti atjungtus grafikus, galime pakartoti aukščiau pateiktą algoritmą viršūnėms, turinčioms atstumas = INFINITY, arba tiesiog nelankomoms viršūnėms.

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

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->Viršūnių skaičius, E-> Kraštinių skaičius int V, E;  // grafikas vaizduojamas kaip briaunų masyvas.  struct Edge* kraštas; }; // Sukuria grafą su V viršūnėmis ir E briaunomis struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  grafikas->V = V;  grafikas->E = E;  grafikas->kraštas = naujas kraštas[E];  grąžinimo grafikas; } // Naudingumo funkcija, naudojama sprendimui spausdinti void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  už (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 = grafikas->E;  int dist[V];  // 1 veiksmas: inicijuokite atstumus nuo src iki visų kitų // viršūnių kaip INFINITE (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->kraštas[j].src;  int v = grafikas->kraštinė[j].dest;  int svoris = grafikas->kraštinė[j].svoris;  if (dist[u] != INT_MAX && dist[u] + svoris< 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->edge[i].src;  int v = grafikas->kraštinė[i].dest;  int svoris = grafikas->kraštinė[i].svoris;  if (dist[u] != INT_MAX && dist[u] + svoris< 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->kraštas[0].src = 0;  grafikas->kraštas[0].dest = 1;  grafikas->kraštas[0].svoris = -1;  // pridėti kraštą 0-2 (arba A-C aukščiau esančiame paveikslėlyje) grafas->kraštinė[1].src = 0;  grafikas->kraštas[1].dest = 2;  grafikas->kraštas[1].svoris = 4;  // pridėti kraštą 1-2 (arba B-C aukščiau esančiame paveikslėlyje) grafas->kraštinė[2].src = 1;  grafikas->kraštas[2].dest = 2;  grafikas->kraštas[2].svoris = 3;  // pridėti kraštą 1-3 (arba B-D aukščiau esančiame paveikslėlyje) grafas->kraštas[3].src = 1;  grafikas->kraštas[3].dest = 3;  grafikas->kraštas[3].svoris = 2;  // pridėti kraštą 1-4 (arba B-E aukščiau esančiame paveikslėlyje) grafas->kraštinė[4].src = 1;  grafikas->kraštas[4].dest = 4;  grafikas->kraštinė[4].svoris = 2;  // pridėti kraštą 3-2 (arba D-C aukščiau esančiame paveikslėlyje) grafas->kraštinė[5].src = 3;  grafikas->kraštas[5].dest = 2;  grafikas->kraštas[5].svoris = 5;  // pridėti kraštą 3-1 (arba D-B aukščiau esančiame paveikslėlyje) grafas->kraštinė[6].src = 3;  grafikas->kraštas[6].dest = 1;  grafikas->kraštas[6].svoris = 1;  // pridėti kraštą 4-3 (arba E-D aukščiau esančiame paveikslėlyje) grafas->kraštas[7].src = 4;  grafikas->kraštas[7].dest = 3;  grafikas->kraštas[7].svoris = -3;    // Funkcijos iškvietimas BellmanFord(graph, 0);  grąžinti 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);>
Išvestis 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Bellman-Ford algoritmo sudėtingumo analizė :

  • Laiko sudėtingumas, kai grafikas yra sujungtas:
    • Geriausias atvejis: O (E), kai atstumo masyvas po 1 ir 2 atsipalaidavimo yra vienodas, galime tiesiog sustabdyti tolesnį apdorojimą
    • Vidutinis atvejis: O(V*E)
    • Blogiausiu atveju: O(V*E)
  • Laiko sudėtingumas, kai grafikas yra atjungtas :
    • Visi atvejai: O(E*(V^2))
  • Pagalbinė erdvė: O(V), kur V yra grafiko viršūnių skaičius.

„Bellman Ford“ algoritmų programos:

  • Tinklo maršrutas: „Bellman-Ford“ naudojamas kompiuterių tinkluose, siekiant rasti trumpiausius kelius maršruto lentelėse, padedant duomenų paketams efektyviai naršyti tinkluose.
  • GPS navigacija: GPS įrenginiai naudoja „Bellman-Ford“, kad apskaičiuotų trumpiausius arba greičiausius maršrutus tarp vietovių, padėdami navigacijos programoms ir įrenginiams.
  • Transportas ir logistika: Bellman-Ford algoritmas gali būti taikomas siekiant nustatyti optimalius transporto ir logistikos kelius, sumažinant degalų sąnaudas ir kelionės laiką.
  • Žaidimo kūrimas: „Bellman-Ford“ gali būti naudojamas modeliuojant judėjimą ir navigaciją virtualiuose žaidimų kūrimo pasauliuose, kur skirtingi keliai gali turėti skirtingas išlaidas ar kliūtis.
  • Robotika ir autonominės transporto priemonės: Algoritmas padeda planuoti robotų ar autonominių transporto priemonių kelią, atsižvelgiant į kliūtis, reljefą ir energijos suvartojimą.

Bellmano Fordo algoritmo trūkumas:

  • Bellman-Ford algoritmas nepavyks, jei grafike yra koks nors neigiamas briaunų ciklas.

Susiję straipsniai apie vieno šaltinio trumpiausio kelio algoritmus: