logo

TechCodeview

Bellman-Ford-algoritmi

Kuvittele, että sinulla on kartta eri kaupungeista, joita yhdistää tiet, joista jokaisella on tietty etäisyys. The Bellman-Ford-algoritmi on kuin opas, joka auttaa sinua löytämään lyhimmän polun kaupungista kaikkiin muihin kaupunkeihin, vaikka joidenkin teiden pituus olisi negatiivinen. Se on kuin a GPS tietokoneille, hyödyllinen, kun haluat selvittää nopeimman tavan päästä pisteestä toiseen verkossa. Tässä artikkelissa tarkastelemme tarkemmin, miten tämä algoritmi toimii ja miksi se on niin kätevä jokapäiväisten ongelmien ratkaisemisessa.

Bellman-Ford-algoritmi

Sisällysluettelo



Bellman-Ford -algoritmi

Bellman-Ford on ainoa lähde lyhimmän polun algoritmi, joka määrittää lyhimmän polun tietyn lähdepisteen ja graafin jokaisen toisen kärjen välillä. Tätä algoritmia voidaan käyttää molemmissa painotettu ja painottamaton kaavioita.

kali linux terminaali

A Bellman-Ford Algoritmi löytää myös lyhimmän polun kaaviosta, kuten Dijkstran algoritmi . Vaikka Bellman-Ford on hitaampi kuin Dijkstran algoritmi , se pystyy käsittelemään kaavioita negatiiviset reunapainot , mikä tekee siitä monipuolisemman. Lyhintä polkua ei löydy, jos on olemassa a negatiivinen sykli kaaviossa. Jos jatkamme negatiivisen syklin kiertämistä äärettömän monta kertaa, niin polun hinta laskee edelleen (vaikka polun pituus kasvaa). Tuloksena, Bellman-Ford pystyy myös havaitsemaan negatiiviset syklit , joka on tärkeä ominaisuus.

Idea Bellman Ford -algoritmin takana:

Bellman-Ford-algoritmin pääperiaate on, että se alkaa yhdestä lähteestä ja laskee etäisyyden jokaiseen solmuun. Etäisyys on aluksi tuntematon ja sen oletetaan olevan ääretön, mutta ajan kuluessa algoritmi rentouttaa näitä polkuja tunnistamalla muutamia lyhyempiä polkuja. Siksi sanotaan, että Bellman-Ford perustuu Rentoutumisen periaate .

Bellman-Fordin reunojen rentouttamisperiaate:

  • Siinä todetaan, että kaaviolle, jolla on N kärjet, kaikkien reunojen tulee olla rentoina N-1 kertaa yhden lähteen lyhimmän polun laskemiseksi.
  • Sen havaitsemiseksi, onko negatiivinen sykli olemassa vai ei, löysää kaikki reunat vielä kerran ja jos minkä tahansa solmun lyhin etäisyys pienenee, voidaan sanoa, että negatiivinen sykli on olemassa. Lyhyesti sanottuna, jos löysämme reunat N kertaa, ja minkä tahansa solmun lyhin etäisyys muuttuu N-1 ja Nth rentoutumista kuin negatiivinen sykli on olemassa, muuten ei ole olemassa.

Miksi Relaxing Edges N-1 kertaa antaa meille yhden lähteen lyhimmän polun?

Pahimmassa tapauksessa lyhin polku kahden kärjen välillä voi olla korkeintaan N-1 reunat, missä N on pisteiden lukumäärä. Tämä johtuu siitä, että kaaviossa on yksinkertainen polku N huipuilla voi olla korkeintaan N-1 reunat, koska on mahdotonta muodostaa suljettua silmukkaa käymättä uudelleen kärjessä.

Rentouttamalla reunoja N-1 kertaa, Bellman-Ford-algoritmi varmistaa, että kaikkien kärkien etäisyysarviot on päivitetty optimaalisiin arvoihinsa olettaen, että kuvaaja ei sisällä negatiivisen painotuksen jaksoja, jotka ovat saavutettavissa lähdepisteestä. Jos graafi sisältää negatiivisen painon syklin, joka on saavutettavissa lähdepisteestä, algoritmi voi havaita sen N-1 iteraatioita, koska negatiivinen sykli katkaisee lyhimmän polun.

Yhteenvetona, rentouttavat reunat N-1 kertaa Bellman-Ford-algoritmissa takaa, että algoritmi on tutkinut kaikki mahdolliset pituuspolut aina N-1 , joka on kaavion lyhimmän polun suurin mahdollinen pituus N kärjet. Tämän ansiosta algoritmi voi laskea oikein lyhimmät polut lähdepisteestä kaikkiin muihin kärkipisteisiin, kun otetaan huomioon, että negatiivisia syklejä ei ole.

Miksi etäisyyden pienentäminen N:nnessä rentoutumisessa osoittaa negatiivisen syklin olemassaolon?

Kuten aiemmin keskusteltiin, yhden lähteen lyhimpien polkujen saavuttaminen kaikkiin muihin solmuihin kestää N-1 rentoutumista. Jos N:s relaksaatio pienentää entisestään minkä tahansa solmun lyhimmän etäisyyden, se tarkoittaa, että tietty negatiivinen painoinen reuna on ajettu vielä kerran. On tärkeää huomata, että aikana N-1 relaksaatioita, oletimme, että kukin kärkipiste kulkee vain kerran. Etäisyyden pieneneminen N:nnen rentoutumisen aikana osoittaa kuitenkin uudelleenkäynnin kärjessä.

Bellman-Ford-algoritmin toiminta negatiivisen syklin havaitsemiseksi kaaviossa:

Oletetaan, että meillä on alla oleva kaavio ja haluamme selvittää, onko negatiivinen sykli olemassa vai ei, käyttämällä Bellman-Fordia.

Alkuperäinen kaavio

Vaihe 1: Alusta etäisyystaulukko Dist[] tallentaaksesi kunkin kärjen lyhimmän etäisyyden lähdepisteestä. Aluksi lähteen etäisyys on 0 ja muiden kärkien etäisyys on INFINITY.

java do while esimerkki

Alusta etäisyystaulukko

Vaihe 2: Aloita reunojen rentouttaminen ensimmäisen rentoutumisen aikana:

  • B:n nykyinen etäisyys> (A:n etäisyys) + (A:n paino: B:hen) eli ääretön> 0 + 5
    • Siksi Dist[B] = 5

1. Rentoutuminen

Vaihe 3: Toisen rentoutumisen aikana:
  • Nykyinen D:n etäisyys> (B:n etäisyys) + (B:n ja D:n paino) eli ääretön> 5 + 2
    • Dist[D] = 7
  • C:n nykyinen etäisyys> (B:n etäisyys) + (B:n ja C:n paino) eli ääretön> 5 + 1
    • Dist[C] = 6

2. rentoutuminen

muuntaa merkkijonon päivämäärä

Vaihe 4: Kolmannen rentoutumisen aikana:

  • Nykyinen etäisyys F> (etäisyys D ) + (D:n paino F) eli ääretön> 7 + 2
    • Dist[F] = 9
  • Nykyinen etäisyys E> (C etäisyys ) + (C:n paino E) eli ääretön> 6 + 1
    • Väli[E] = 7

3. rentoutuminen

Vaihe 5: Neljännen rentoutumisen aikana:

  • Nykyinen etäisyys D> (Etäisyys E) + (E:n paino D:hen) eli 7> 7 + (-1)
    • Dist[D] = 6
  • Nykyinen etäisyys E> (etäisyys F ) + (F:n paino E) eli 7> 9 + (-3)
    • Väli[E] = 6

4. Rentoutuminen

Vaihe 6: 5. rentoutumisen aikana:

  • Nykyinen etäisyys F> (etäisyys D) + (D:n paino F) eli 9> 6 + 2
    • Dist[F] = 8
  • Nykyinen etäisyys D> (Etäisyys E ) + (E:n paino D:hen) eli 6> 6 + (-1)
    • Dist[D] = 5
  • Koska graafissa h 6 kärkeä, Joten 5. relaksaation aikana olisi pitänyt laskea lyhin etäisyys kaikille pisteille.

Viides rentoutuminen

Vaihe 7: Nyt viimeisen relaksaation eli kuudennen relaksaation pitäisi osoittaa negatiivisen syklin olemassaoloa, jos viidennen rentoutumisen etäisyysmatriisissa on muutoksia.

Kuudennen rentoutumisen aikana voidaan nähdä seuraavat muutokset:

  • Nykyinen etäisyys E> (etäisyys F) + (F:n paino E) eli 6> 8 + (-3)
    • Väli[E]=5
  • Nykyinen etäisyys F> (Distance of D ) + (D:n paino F) eli 8> 5 + 2
    • Väli[F]=7

Koska tarkkailemme muutoksia Distance-taulukossa, voimme siis päätellä negatiivisen syklin olemassaolon kaaviossa.

6. Rentoutuminen

ääretön silmukka

Tulos: Kaaviossa on negatiivinen sykli (D->F->E).

Algoritmi negatiivisen syklin löytämiseksi suunnatusta painotetusta kaaviosta Bellman-Fordin avulla:

  • Alusta etäisyystaulukko dist[] jokaiselle kärkipisteelle ' sisään ' kuten dist[v] = INFINITY .
  • Oletetaan mikä tahansa kärkipiste (oletetaan '0') lähteeksi ja määritetään dist = 0 .
  • Rentoudu kaikki reunat(u,v,paino) N-1 kertaa alla olevan ehdon mukaisesti:
    • etäisyys[v] = minimi(etäisyys[v], etäisyys[u] + paino)
  • Rentouta nyt kaikki reunat vielä kerran, eli Nth ajan ja alla olevien kahden tapauksen perusteella voimme havaita negatiivisen syklin:
    • Tapaus 1 (Negatiivinen sykli olemassa): Kaikille reuna(u, v, paino), jos väli[u] + paino
    • Tapaus 2 (ei negatiivista sykliä): tapaus 1 epäonnistuu kaikilla reunoilla.

Irrotettujen kuvaajien käsittely algoritmissa:

Yllä oleva algoritmi ja ohjelma eivät välttämättä toimi, jos annettu graafi on irrotettu. Se toimii, kun kaikki kärjet ovat saavutettavissa lähdepisteestä 0 .
Käsittelemään irrotettuja kaavioita, voimme toistaa yllä olevan algoritmin pisteille, joilla on etäisyys = INFINITY, tai vain pisteille, joissa ei käy.

Alla on yllä olevan lähestymistavan toteutus:

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->Piikkien lukumäärä, E-> Reunojen lukumäärä int V, E;  // graafi esitetään reunojen joukkona.  struct Edge* reuna; }; // Luo graafin V-pisteillä ja E-reunalla struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graafi->V = V;  graafi->E = E;  kaavio->reuna = uusi reuna[E];  paluukaavio; } // Aputoiminto, jolla tulostetaan ratkaisu void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  for (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 = graafi->E;  int dist[V];  // Vaihe 1: Alusta etäisyydet src:stä kaikkiin muihin // kärkipisteisiin INFINITE-arvoksi (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->reuna[j].src;  int v = kaavio->reuna[j].kohde;  int paino = kaavio->reuna[j].paino;  if (dist[u] != INT_MAX && dist[u] + paino< 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 = kaavio->reuna[i].dest;  int paino = kaavio->reuna[i].paino;  if (dist[u] != INT_MAX && dist[u] + paino< 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->reuna[0].src = 0;  kaavio->reuna[0].kohde = 1;  kaavio->reuna[0].paino = -1;  // lisää reuna 0-2 (tai A-C yllä olevassa kuvassa) graph->edge[1].src = 0;  kaavio->reuna[1].kohde = 2;  kaavio->reuna[1].paino = 4;  // lisää reuna 1-2 (tai B-C yllä olevassa kuvassa) graph->edge[2].src = 1;  kaavio->reuna[2].kohde = 2;  kaavio->reuna[2].paino = 3;  // lisää reuna 1-3 (tai B-D yllä olevassa kuvassa) graph->edge[3].src = 1;  kaavio->reuna[3].kohde = 3;  kaavio->reuna[3].paino = 2;  // lisää reuna 1-4 (tai B-E yllä olevassa kuvassa) graph->edge[4].src = 1;  kaavio->reuna[4].kohde = 4;  kaavio->reuna[4].paino = 2;  // lisää reuna 3-2 (tai D-C yllä olevassa kuvassa) graph->edge[5].src = 3;  kaavio->reuna[5].kohde = 2;  kaavio->reuna[5].paino = 5;  // lisää reuna 3-1 (tai D-B yllä olevassa kuvassa) graph->edge[6].src = 3;  kaavio->reuna[6].kohde = 1;  kaavio->reuna[6].paino = 1;  // lisää reuna 4-3 (tai E-D yllä olevassa kuvassa) graph->edge[7].src = 4;  kaavio->reuna[7].kohde = 3;  kaavio->reuna[7].paino = -3;    // Funktiokutsu BellmanFord(kaavio, 0);  paluu 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>
Python 3 
# 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);>
Lähtö 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Bellman-Ford-algoritmin monimutkaisuusanalyysi :

  • Aika monimutkaisuus, kun kuvaaja on yhdistetty:
    • Paras tapaus: O(E), kun etäisyystaulukko 1. ja 2. rentoutumisen jälkeen ovat samat, voimme yksinkertaisesti lopettaa jatkokäsittelyn
    • Keskimääräinen tapaus: O(V*E)
    • Pahimmassa tapauksessa: O(V*E)
  • Aika monimutkaisuus, kun kuvaaja on irrotettu :
    • Kaikki tapaukset: O(E*(V^2))
  • Aputila: O(V), missä V on graafin kärkien lukumäärä.

Bellman Fordin algoritmisovellukset:

  • Verkkoreititys: Bellman-Fordia käytetään tietokoneverkoissa lyhimpien polkujen löytämiseen reititystaulukoista, mikä auttaa datapaketteja navigoimaan tehokkaasti verkkojen välillä.
  • GPS-navigointi: GPS-laitteet käyttävät Bellman-Fordia laskeakseen lyhimmät tai nopeimmat reitit sijaintien välillä, mikä auttaa navigointisovelluksia ja -laitteita.
  • Kuljetus ja logistiikka: Bellman-Fordin algoritmia voidaan soveltaa ajoneuvojen optimaalisten reittien määrittämiseen kuljetuksissa ja logistiikassa, minimoiden polttoaineen kulutus ja matka-aika.
  • Pelikehitys: Bellman-Fordilla voidaan mallintaa liikettä ja navigointia virtuaalimaailmoissa pelikehityksen aikana, jossa eri poluilla voi olla erilaisia ​​kustannuksia tai esteitä.
  • Robotiikka ja autonomiset ajoneuvot: Algoritmi auttaa robottien tai autonomisten ajoneuvojen reitin suunnittelussa, ottaen huomioon esteet, maaston ja energiankulutuksen.

Bellman Fordin algoritmin haittapuoli:

  • Bellman-Ford-algoritmi epäonnistuu, jos kuvaaja sisältää negatiivisen reunajakson.

Aiheeseen liittyviä artikkeleita yhden lähteen lyhimmän polun algoritmeista: