logo

TechCodeview

Bellman–Ford-algoritme

Tenk deg at du har et kart med forskjellige byer forbundet med veier, hver vei har en viss avstand. De Bellman–Ford-algoritme er som en guide som hjelper deg å finne den korteste veien fra én by til alle andre byer, selv om noen veier har negative lengder. Det er som en GPS for datamaskiner, nyttig for å finne ut den raskeste måten å komme seg fra ett punkt til et annet i et nettverk. I denne artikkelen skal vi se nærmere på hvordan denne algoritmen fungerer og hvorfor den er så nyttig for å løse hverdagslige problemer.

Bellman-Ford-algoritme

Innholdsfortegnelse



Bellman-Ford algoritme

Bellman-Ford er en eneste kilde korteste vei-algoritme som bestemmer den korteste veien mellom et gitt kildepunkt og annenhver toppunkt i en graf. Denne algoritmen kan brukes på begge vektet og uvektet grafer.

murer formel

EN Bellman-Ford algoritmen vil garantert finne den korteste veien i en graf, tilsvarende Dijkstras algoritme . Selv om Bellman-Ford er tregere enn Dijkstras algoritme , den er i stand til å håndtere grafer med negative kantvekter , noe som gjør den mer allsidig. Den korteste veien kan ikke finnes hvis det finnes en negativ syklus i grafen. Hvis vi fortsetter å gå rundt den negative syklusen et uendelig antall ganger, så vil kostnaden for stien fortsette å synke (selv om lengden på stien øker). Som et resultat, Bellman-Ford er også i stand til å oppdage negative sykluser , som er en viktig funksjon.

Ideen bak Bellman Ford Algorithm:

Bellman-Ford-algoritmens primære prinsipp er at den starter med en enkelt kilde og beregner avstanden til hver node. Avstanden er i utgangspunktet ukjent og antas å være uendelig, men etter hvert som tiden går, slapper algoritmen av disse banene ved å identifisere noen kortere baner. Derfor sies det at Bellman-Ford er basert på Prinsippet om avslapning .

Prinsippet for avslapning av kanter for Bellman-Ford:

  • Det står at for grafen har N hjørner, bør alle kanter være avslappet N-1 ganger for å beregne den korteste veien for enkeltkilden.
  • For å oppdage om en negativ syklus eksisterer eller ikke, slapp av hele kanten en gang til, og hvis den korteste avstanden for en node reduseres, kan vi si at det eksisterer en negativ syklus. Kort sagt hvis vi slapper av på kantene N ganger, og det er noen endring i den korteste avstanden til en node mellom N-1 og Nth avslapping enn en negativ syklus eksisterer, ellers ikke eksisterer.

Hvorfor Relaxing Edges N-1 ganger, gir oss Single Source Shortest Path?

I verste fall kan en korteste vei mellom to hjørner ha på det meste N-1 kanter, hvor N er antall toppunkter. Dette er fordi en enkel bane i en graf med N toppunkter kan ha på det meste N-1 kanter, da det er umulig å danne en lukket sløyfe uten å gå tilbake til et toppunkt.

Ved å slappe av kanter N-1 ganger sikrer Bellman-Ford-algoritmen at avstandsestimatene for alle toppunktene har blitt oppdatert til deres optimale verdier, forutsatt at grafen ikke inneholder negative vektsykluser som kan nås fra kildetoppunktet. Hvis en graf inneholder en negativ vektsyklus som kan nås fra kildetoppunktet, kan algoritmen oppdage det etter N-1 iterasjoner, siden den negative syklusen forstyrrer de korteste veilengdene.

Oppsummert, avslappende kanter N-1 ganger i Bellman-Ford-algoritmen garanterer at algoritmen har utforsket alle mulige veier med lengde opp til N-1 , som er den maksimalt mulige lengden på en korteste vei i en graf med N hjørner. Dette gjør at algoritmen kan beregne de korteste veiene fra kildetoppunktet til alle andre toppunkter, gitt at det ikke er noen negative vektsykluser.

Hvorfor indikerer reduksjonen av avstanden i den N'te avslapningen eksistensen av en negativ syklus?

Som tidligere diskutert tar det å oppnå den korteste veien til enkeltkilden til alle andre noder N-1 avslapninger. Hvis den N’te relaksasjonen ytterligere reduserer den korteste avstanden for en node, innebærer det at en viss kant med negativ vekt har blitt krysset igjen. Det er viktig å merke seg at i løpet av N-1 avslapninger, antok vi at hvert toppunkt bare krysses én gang. Imidlertid indikerer reduksjonen av avstanden under den N'te avslapningen at du besøker et toppunkt på nytt.

Arbeid med Bellman-Ford-algoritmen for å oppdage den negative syklusen i grafen:

La oss anta at vi har en graf som er gitt nedenfor, og vi ønsker å finne ut om det eksisterer en negativ syklus eller ikke ved å bruke Bellman-Ford.

Innledende graf

Trinn 1: Initialiser en distansematrise Dist[] for å lagre den korteste avstanden for hvert toppunkt fra kildetoppunktet. Til å begynne med vil avstanden til kilden være 0 og avstanden til andre hjørner vil være UENDELIG.

Initialiser en avstandsgruppe

"hva er forskjellen mellom en løve og en tiger"

Steg 2: Begynn å slappe av kantene under 1. avslapning:

deterministiske endelige automater
  • Gjeldende avstand til B> (Avstand til A) + (vekt av A til B) dvs. uendelig> 0 + 5
    • Derfor er Dist[B] = 5

1. avslapning

Trinn 3: Under 2. avslapning:
  • Nåværende avstand til D> (avstand til B) + (vekt av B til D) dvs. uendelig> 5 + 2
    • Avstand[D] = 7
  • Nåværende avstand til C> (avstand til B) + (vekt av B til C) dvs. uendelig> 5 + 1
    • Avstand[C] = 6

2. avslapning

Trinn 4: Under 3. avslapning:

  • Nåværende avstand til F> (avstand til D ) + (vekt av D til F) dvs. uendelig> 7 + 2
    • Avstand[F] = 9
  • Nåværende avstand til E> (avstand til C ) + (vekt av C til E) dvs. uendelig> 6 + 1
    • Avstand[E] = 7

3. avslapning

Trinn 5: Under 4. avslapning:

  • Nåværende avstand til D> (avstand til E) + (vekt av E til D) dvs. 7> 7 + (-1)
    • Avstand[D] = 6
  • Nåværende avstand til E> (avstand til F ) + (vekt av F til E) dvs. 7> 9 + (-3)
    • Avstand[E] = 6

4. Avslapping

Trinn 6: Under 5. avslapning:

  • Nåværende avstand til F> (avstand til D) + (vekt av D til F) dvs. 9> 6 + 2
    • Avstand[F] = 8
  • Nåværende avstand til D> (avstand til E ) + (vekt av E til D) dvs. 6> 6 + (-1)
    • Avstand[D] = 5
  • Siden grafen h 6 toppunkter, så under den 5. relaksasjonen burde den korteste avstanden for alle toppunktene vært beregnet.

5. Avslapping

Trinn 7: Nå bør den endelige avspenningen, dvs. den 6. avspenningen, indikere tilstedeværelsen av negativ syklus hvis det er noen endringer i avstandsgruppen for 5. avslapning.

Under den 6. avspenningen kan følgende endringer sees:

  • Nåværende avstand til E> (avstand til F) + (vekt av F til E) dvs. 6> 8 + (-3)
    • Avstand[E]=5
  • Nåværende avstand til F> (avstand til D ) + (vekt av D til F) dvs. 8> 5 + 2
    • Avstand[F]=7

Siden vi observerer endringer i avstandsmatrisen. Derfor kan vi konkludere med tilstedeværelsen av en negativ syklus i grafen.

6. Avslapping

forberede seg på test mockito

Resultat: En negativ syklus (D->F->E) eksisterer i grafen.

Algoritme for å finne negativ syklus i en rettet vektet graf ved å bruke Bellman-Ford:

  • Initialiser avstandsarray dist[] for hvert toppunkt ' i ' som dist[v] = UENDELIG .
  • Anta et hvilket som helst toppunkt (la oss si '0') som kilde og tilordne dist = 0 .
  • Slapp av alt kanter(u,v,vekt) N-1 ganger i henhold til betingelsen nedenfor:
    • dist[v] = minimum(avstand[v], avstand[u] + vekt)
  • Nå, slapp av alle kantene en gang til, dvs Nth tid og basert på de to tilfellene nedenfor kan vi oppdage den negative syklusen:
    • Tilfelle 1 (negativ syklus eksisterer): For evt kant(u, v, vekt), hvis dist[u] + vekt
    • Tilfelle 2 (Ingen negativ syklus): Tilfelle 1 mislykkes for alle kantene.

Håndtere frakoblede grafer i algoritmen:

Algoritmen og programmet ovenfor fungerer kanskje ikke hvis den gitte grafen er frakoblet. Det fungerer når alle hjørner er tilgjengelige fra kilden 0 .
For å håndtere frakoblede grafer, kan vi gjenta algoritmen ovenfor for toppunkter som har avstand = UENDELIG, eller rett og slett for hjørnene som ikke er besøkt.

Nedenfor er implementeringen av tilnærmingen ovenfor:

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->Antall hjørner, E-> Antall kanter int V, E;  // grafen er representert som en rekke kanter.  struct Edge* edge; }; // Lager en graf med V-punkt og E-kanter struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graf->V = V;  graf->E = E;  graph->edge = new Edge[E];  retur graf; } // En verktøyfunksjon som brukes til å skrive ut løsningen 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 = graf->E;  int dist[V];  // Trinn 1: Initialiser avstander fra src til alle andre // toppunkter som UENDELIG 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->kant[j].kilde;  int v = graf->kant[j].dest;  int vekt = graf->kant[j].vekt;  if (avstand[u] != INT_MAX && dist[u] + vekt< 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->kant[i].kilde;  int v = graf->kant[i].dest;  int vekt = graf->kant[i].vekt;  if (avstand[u] != INT_MAX && dist[u] + vekt< 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->kant[0].kilde = 0;  graf->kant[0].dest = 1;  graf->kant[0].vekt = -1;  // legg til kant 0-2 (eller A-C i figuren ovenfor) graf->kant[1].src = 0;  graf->kant[1].dest = 2;  graf->kant[1].vekt = 4;  // legg til kant 1-2 (eller B-C i figuren ovenfor) graph->edge[2].src = 1;  graf->kant[2].dest = 2;  graf->kant[2].vekt = 3;  // legg til kant 1-3 (eller B-D i figuren ovenfor) graph->edge[3].src = 1;  graf->kant[3].dest = 3;  graf->kant[3].vekt = 2;  // legg til kant 1-4 (eller B-E i figuren ovenfor) graph->edge[4].src = 1;  graf->kant[4].dest = 4;  graf->kant[4].vekt = 2;  // legg til kant 3-2 (eller D-C i figuren ovenfor) graph->edge[5].src = 3;  graf->kant[5].dest = 2;  graf->kant[5].vekt = 5;  // legg til kant 3-1 (eller D-B i figuren ovenfor) graph->edge[6].src = 3;  graf->kant[6].dest = 1;  graf->kant[6].vekt = 1;  // legg til kant 4-3 (eller E-D i figuren ovenfor) graph->edge[7].src = 4;  graf->kant[7].dest = 3;  graf->kant[7].vekt = -3;    // Funksjonskall BellmanFord(graf, 0);  returner 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);>
Produksjon 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Kompleksitetsanalyse av Bellman-Ford-algoritmen :

  • Tidskompleksitet når grafen er tilkoblet:
    • Beste tilfelle: O(E), når avstandsarrayen etter 1. og 2. avspenning er like, kan vi ganske enkelt stoppe videre behandling
    • Gjennomsnittlig sak: O(V*E)
    • Worst Case: O(V*E)
  • Tidskompleksitet når grafen er frakoblet :
    • Alle sakene: O(E*(V^2))
  • Hjelpeplass: O(V), hvor V er antall toppunkter i grafen.

Bellman Fords algoritmeapplikasjoner:

  • Nettverksruting: Bellman-Ford brukes i datanettverk for å finne de korteste veiene i rutingtabeller, og hjelper datapakker med å navigere effektivt på tvers av nettverk.
  • GPS-navigasjon: GPS-enheter bruker Bellman-Ford til å beregne korteste eller raskeste ruter mellom lokasjoner, og hjelpe navigasjonsapper og enheter.
  • Transport og logistikk: Bellman-Fords algoritme kan brukes til å bestemme de optimale banene for kjøretøy innen transport og logistikk, og minimere drivstofforbruk og reisetid.
  • Spillutvikling: Bellman-Ford kan brukes til å modellere bevegelse og navigering innenfor virtuelle verdener i spillutvikling, hvor ulike veier kan ha varierende kostnader eller hindringer.
  • Robotikk og autonome kjøretøy: Algoritmen hjelper til med veiplanlegging for roboter eller autonome kjøretøy, med tanke på hindringer, terreng og energiforbruk.

Ulempen med Bellman Fords algoritme:

  • Bellman-Ford-algoritmen vil mislykkes hvis grafen inneholder en negativ kantsyklus.

Relaterte artikler om algoritmer for den korteste veien med én kilde: