logo

TechCodeview

Bellman-Ford algoritme

Forestil dig, at du har et kort med forskellige byer forbundet med veje, og hver vej har en vis afstand. Det Bellman-Ford algoritme er som en guide, der hjælper dig med at finde den korteste vej fra én by til alle andre byer, selvom nogle veje har negative længder. Det er ligesom en GPS til computere, nyttigt til at finde ud af den hurtigste måde at komme fra et punkt til et andet i et netværk. I denne artikel vil vi se nærmere på, hvordan denne algoritme fungerer, og hvorfor den er så praktisk til at løse hverdagsproblemer.

Bellman-Ford-algoritme

Indholdsfortegnelse



Bellman-Ford algoritme

Bellman-Ford er en enkelt kilde korteste vej-algoritme, der bestemmer den korteste vej mellem et givet kildepunkt og hvert andet toppunkt i en graf. Denne algoritme kan bruges på begge vægtet og uvægtede grafer.

java har næste

EN Bellman-Ford algoritmen vil med garanti også finde den korteste vej i en graf, svarende til Dijkstras algoritme . Selvom Bellman-Ford er langsommere end Dijkstras algoritme , den er i stand til at håndtere grafer med negative kantvægte , hvilket gør den mere alsidig. Den korteste vej kan ikke findes, hvis der findes en negativ cyklus i grafen. Hvis vi fortsætter med at gå rundt om den negative cyklus et uendeligt antal gange, så vil omkostningerne ved stien fortsætte med at falde (selvom længden af ​​stien er stigende). Som resultat, Bellman-Ford er også i stand til at detektere negative cyklusser , hvilket er en vigtig egenskab.

Idéen bag Bellman Ford Algorithm:

Bellman-Ford-algoritmens primære princip er, at den starter med en enkelt kilde og beregner afstanden til hver knude. Afstanden er i første omgang ukendt og antages at være uendelig, men som tiden går, afslapper algoritmen disse stier ved at identificere et par kortere stier. Derfor siges det, at Bellman-Ford er baseret på Princippet om afslapning .

Princippet om afslapning af kanter for Bellman-Ford:

  • Det står, at for grafen have N hjørner, skal alle kanter være afslappede N-1 gange for at beregne den korteste vej for enkeltkilden.
  • For at opdage, om der eksisterer en negativ cyklus eller ej, skal du slappe af hele kanten en gang til, og hvis den korteste afstand for en knude reduceres, kan vi sige, at der eksisterer en negativ cyklus. Kort sagt hvis vi slapper af i kanterne N gange, og der er nogen ændring i den korteste afstand af enhver node mellem N-1th og Nth afslapning end en negativ cyklus eksisterer, ellers ikke eksisterer.

Hvorfor Relaxing Edges N-1 gange, giver os Single Source Shortest Path?

I det værste tilfælde kan en korteste vej mellem to hjørner højst have N-1 kanter, hvor N er antallet af hjørner. Dette skyldes, at en simpel sti i en graf med N hjørner kan højst have N-1 kanter, da det er umuligt at danne en lukket løkke uden at gense et toppunkt.

Ved afslappende kanter N-1 gange sikrer Bellman-Ford-algoritmen, at afstandsestimaterne for alle toppunkter er blevet opdateret til deres optimale værdier, forudsat at grafen ikke indeholder negative vægtcyklusser, der kan nås fra kildens toppunkt. Hvis en graf indeholder en negativ vægtcyklus, der kan nås fra kildens toppunkt, kan algoritmen detektere det efter N-1 iterationer, da den negative cyklus forstyrrer de korteste vejlængder.

Sammenfattende, afslappende kanter N-1 gange i Bellman-Ford-algoritmen garanterer, at algoritmen har udforsket alle mulige veje af længde op til N-1 , som er den maksimalt mulige længde af en korteste vej i en graf med N hjørner. Dette gør det muligt for algoritmen at beregne de korteste veje fra kildens toppunkt til alle andre toppunkter korrekt, givet at der ikke er nogen negative vægtcyklusser.

Hvorfor indikerer reduktionen af ​​afstanden i den N'te afslapning eksistensen af ​​en negativ cyklus?

Som tidligere diskuteret kræver det at opnå de korteste veje til alle andre knudepunkter N-1 afslapninger. Hvis den N'te afslapning yderligere reducerer den korteste afstand for en hvilken som helst knude, indebærer det, at en vis kant med negativ vægt er blevet krydset endnu en gang. Det er vigtigt at bemærke, at i løbet af N-1 afslapninger, antog vi, at hvert toppunkt kun krydses én gang. Reduktionen af ​​afstanden under den N'te afslapning indikerer dog, at man genbesøger et toppunkt.

Arbejde med Bellman-Ford Algorithm til at detektere den negative cyklus i grafen:

Lad os antage, at vi har en graf, som er givet nedenfor, og vi ønsker at finde ud af, om der eksisterer en negativ cyklus eller ej ved at bruge Bellman-Ford.

Indledende graf

Trin 1: Initialiser en afstandsmatrix Dist[] for at gemme den korteste afstand for hvert toppunkt fra kildepunktet. Indledningsvis vil afstanden til kilden være 0, og afstanden til andre hjørner vil være UENDELIG.

Initialiser et afstandsarray

8 til 1 multiplekser

Trin 2: Begynd at slappe af kanterne under 1. afslapning:

10 ml til ounces
  • Aktuel afstand af B> (Afstand af A) + (vægt af A til B) dvs. uendelig> 0 + 5
    • Derfor er Dist[B] = 5

1. afslapning

Trin 3: Under 2. afslapning:
  • Aktuel afstand af D> (Afstand af B) + (vægt af B til D) dvs. uendelig> 5 + 2
    • Afstand[D] = 7
  • Aktuel afstand af C> (Afstand af B) + (vægt af B til C), dvs. uendelig> 5 + 1
    • Afstand[C] = 6

2. Afslapning

Trin 4: Under 3. afslapning:

  • Aktuel afstand af F> (Afstand af D ) + (vægt af D til F) dvs. uendelig> 7 + 2
    • Afstand[F] = 9
  • Aktuel afstand af E> (Afstand af C ) + (vægt af C til E) dvs. uendelig> 6 + 1
    • Afstand[E] = 7

3. Afslapning

Trin 5: Under 4. afslapning:

  • Aktuel afstand af D> (Afstand af E) + (vægt af E til D), dvs. 7> 7 + (-1)
    • Afstand[D] = 6
  • Aktuel afstand af E> (Afstand af F ) + (vægt af F til E), dvs. 7> 9 + (-3)
    • Afstand[E] = 6

4. Afslapning

Trin 6: Under 5. afslapning:

  • Aktuel afstand af F> (Afstand af D) + (vægt af D til F), dvs. 9> 6 + 2
    • Afstand[F] = 8
  • Aktuel afstand af D> (Afstand af E ) + (vægt af E til D), dvs. 6> 6 + (-1)
    • Afstand[D] = 5
  • Siden grafen h 6 hjørner, så under den 5. afslapning skulle den korteste afstand for alle hjørnerne være blevet beregnet.

5. Afslapning

Trin 7: Nu skulle den endelige afslapning, dvs. den 6. afslapning, angive tilstedeværelsen af ​​negativ cyklus, hvis der er nogen ændringer i afstandsarrayet for 5. afslapning.

Under den 6. afspænding kan følgende ændringer ses:

  • Aktuel afstand af E> (Afstand af F) + (Vægt af F til E), dvs. 6> 8 + (-3)
    • Afstand[E]=5
  • Aktuel afstand af F> (Afstand af D ) + (vægt af D til F) dvs. 8> 5 + 2
    • Afstand[F]=7

Da vi observerer ændringer i afstandsarrayet. Derfor kan vi konkludere tilstedeværelsen af ​​en negativ cyklus i grafen.

6. Afslapning

java-strengen indeholder

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

Algoritme til at finde negativ cyklus i en rettet vægtet graf ved hjælp af Bellman-Ford:

  • Initialiser distance array dist[] for hvert vertex ' i ' som dist[v] = UENDELIG .
  • Antag et hvilket som helst toppunkt (lad os sige '0') som kilde og tildel dist = 0 .
  • Slap af alt det kanter (u,v,vægt) N-1 gange i henhold til nedenstående betingelse:
    • dist[v] = minimum(afstand[v], afstand[u] + vægt)
  • Slap nu af på alle kanterne en gang til, dvs Nth tid og baseret på nedenstående to tilfælde kan vi opdage den negative cyklus:
    • Tilfælde 1 (negativ cyklus findes): For evt kant(u, v, vægt), hvis dist[u] + vægt
    • Tilfælde 2 (ingen negativ cyklus): Tilfælde 1 mislykkes for alle kanter.

Håndtering af afbrudte grafer i algoritmen:

Ovenstående algoritme og program virker muligvis ikke, hvis den givne graf er afbrudt. Det virker, når alle toppunkter er tilgængelige fra kildens toppunkt 0 .
For at håndtere afbrudte grafer kan vi gentage ovenstående algoritme for toppunkter afstand = UENDELIG, eller blot for de hjørner, der ikke er besøgt.

Nedenfor er implementeringen af ​​ovenstående tilgang:

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->Antal hjørner, E-> Antal kanter int V, E;  // graf er repræsenteret som en række kanter.  struct Kant* kant; }; // Opretter en graf med V-spidser og E-kanter struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graf->V = V;  graf->E = E;  graf->kant = ny kant[E];  retur graf; } // En hjælpefunktion, der bruges til at udskrive 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];  // Trin 1: Initialiser afstande 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 vægt = graf->kant[j].vægt;  hvis (dist[u] != INT_MAX && dist[u] + vægt< 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 vægt = graf->kant[i].vægt;  hvis (dist[u] != INT_MAX && dist[u] + vægt< 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].vægt = -1;  // tilføje kant 0-2 (eller A-C i ovenstående figur) graf->kant[1].src = 0;  graf->kant[1].dest = 2;  graf->kant[1].vægt = 4;  // tilføje kant 1-2 (eller B-C i ovenstående figur) graf->kant[2].src = 1;  graf->kant[2].dest = 2;  graf->kant[2].vægt = 3;  // tilføje kant 1-3 (eller B-D i ovenstående figur) graf->kant[3].src = 1;  graf->kant[3].dest = 3;  graf->kant[3].vægt = 2;  // tilføje kant 1-4 (eller B-E i ovenstående figur) graf->kant[4].src = 1;  graf->kant[4].dest = 4;  graf->kant[4].vægt = 2;  // tilføje kant 3-2 (eller D-C i ovenstående figur) graf->kant[5].src = 3;  graf->kant[5].dest = 2;  graf->kant[5].vægt = 5;  // tilføje kant 3-1 (eller D-B i ovenstående figur) graf->kant[6].src = 3;  graf->kant[6].dest = 1;  graf->kant[6].vægt = 1;  // tilføje kant 4-3 (eller E-D i ovenstående figur) graf->kant[7].src = 4;  graf->kant[7].dest = 3;  graf->kant[7].vægt = -3;    // Funktionskald BellmanFord(graf, 0);  retur 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);>
Produktion 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Kompleksitetsanalyse af Bellman-Ford-algoritmen :

  • Tidskompleksitet, når grafen er forbundet:
    • Bedste tilfælde: O(E), når afstandsarray efter 1. og 2. afslapning er ens, kan vi simpelthen stoppe yderligere behandling
    • Gennemsnitligt tilfælde: O(V*E)
    • Worst Case: O(V*E)
  • Tidskompleksitet, når grafen er afbrudt :
    • Alle sager: O(E*(V^2))
  • Hjælpeplads: O(V), hvor V er antallet af hjørner i grafen.

Bellman Fords algoritmeapplikationer:

  • Netværksrouting: Bellman-Ford bruges i computernetværk til at finde de korteste veje i routingtabeller, hvilket hjælper datapakker med at navigere effektivt på tværs af netværk.
  • GPS-navigation: GPS-enheder bruger Bellman-Ford til at beregne den korteste eller hurtigste rute mellem lokationer, hvilket hjælper med navigationsapps og -enheder.
  • Transport og logistik: Bellman-Fords algoritme kan anvendes til at bestemme de optimale veje for køretøjer inden for transport og logistik, hvilket minimerer brændstofforbrug og rejsetid.
  • Spiludvikling: Bellman-Ford kan bruges til at modellere bevægelse og navigation inden for virtuelle verdener i spiludvikling, hvor forskellige veje kan have varierende omkostninger eller forhindringer.
  • Robotteknologi og autonome køretøjer: Algoritmen hjælper med stiplanlægning for robotter eller autonome køretøjer under hensyntagen til forhindringer, terræn og energiforbrug.

Ulempen ved Bellman Fords algoritme:

  • Bellman-Ford-algoritmen vil mislykkes, hvis grafen indeholder en negativ kantcyklus.

Relaterede artikler om algoritmer for den korteste vej med en enkelt kilde: