logo

TechCodeview

Bellman–Ford Algoritm

Föreställ dig att du har en karta med olika städer sammankopplade med vägar, varje väg har ett visst avstånd. De Bellman–Ford algoritm är som en guide som hjälper dig att hitta den kortaste vägen från en stad till alla andra städer, även om vissa vägar har negativa längder. Det är som en GPS för datorer, användbart för att ta reda på det snabbaste sättet att ta sig från en punkt till en annan i ett nätverk. I den här artikeln kommer vi att titta närmare på hur den här algoritmen fungerar och varför den är så praktisk för att lösa vardagliga problem.

Bellman-Ford-algoritm

Innehållsförteckning



Bellman-Fords algoritm

Bellman-Ford är en enda källa algoritm för kortaste väg som bestämmer den kortaste vägen mellan en given källpunkt och varannan hörn i en graf. Denna algoritm kan användas på båda viktad och oviktad grafer.

java nollkontroll

A Bellman-Ford algoritmen kommer garanterat att hitta den kortaste vägen i en graf, liknande Dijkstras algoritm . Även om Bellman-Ford är långsammare än Dijkstras algoritm , den kan hantera grafer med negativa kantvikter , vilket gör den mer mångsidig. Den kortaste vägen kan inte hittas om det finns en negativ cykel i grafen. Om vi ​​fortsätter att gå runt den negativa cykeln ett oändligt antal gånger, så kommer kostnaden för vägen att fortsätta att minska (även om vägens längd ökar). Som ett resultat, Bellman-Ford är också kapabel att upptäcka negativa cykler , vilket är en viktig egenskap.

Idén bakom Bellman Ford Algorithm:

Bellman-Ford-algoritmens primära princip är att den börjar med en enda källa och beräknar avståndet till varje nod. Avståndet är initialt okänt och antas vara oändligt, men allteftersom tiden går slappnar algoritmen av dessa vägar genom att identifiera några kortare vägar. Därför sägs det att Bellman-Ford bygger på Principen för avkoppling .

Principen för avslappning av kanter för Bellman-Ford:

  • Det står att för grafen som har N hörn, alla kanter ska vara avslappnade N-1 gånger för att beräkna den enstaka källans kortaste väg.
  • För att upptäcka om en negativ cykel existerar eller inte, koppla av hela kanten en gång till och om det kortaste avståndet för någon nod minskar kan vi säga att det finns en negativ cykel. Kort sagt om vi slappnar av kanterna N gånger, och det finns någon förändring i det kortaste avståndet för någon nod mellan N-1:a och Nth avslappning än en negativ cykel existerar, annars inte existerar.

Varför Relaxing Edges N-1 gånger, ger oss Single Source Shortest Path?

I det värsta scenariot kan en kortaste väg mellan två hörn ha högst N-1 kanter, var N är antalet hörn. Detta beror på att en enkel väg i en graf med N hörn kan ha högst N-1 kanter, eftersom det är omöjligt att bilda en sluten slinga utan att återbesöka en vertex.

Genom avkopplande kanter N-1 gånger säkerställer Bellman-Ford-algoritmen att avståndsuppskattningarna för alla hörn har uppdaterats till deras optimala värden, förutsatt att grafen inte innehåller några negativa viktcykler som kan nås från källpunkten. Om en graf innehåller en negativ viktcykel som kan nås från källpunkten, kan algoritmen upptäcka det efter N-1 iterationer, eftersom den negativa cykeln stör de kortaste väglängderna.

Sammanfattningsvis avkopplande kanter N-1 tider i Bellman-Ford-algoritmen garanterar att algoritmen har utforskat alla möjliga vägar av längd upp till N-1 , vilket är den maximala möjliga längden av en kortaste väg i en graf med N hörn. Detta tillåter algoritmen att korrekt beräkna de kortaste vägarna från källpunkten till alla andra hörn, givet att det inte finns några negativa viktcykler.

Varför indikerar minskningen av avståndet i den N:e avslappningen att det finns en negativ cykel?

Som tidigare diskuterats krävs det att uppnå den enkla källans kortaste vägar till alla andra noder N-1 avkopplingar. Om den N:e avslappningen ytterligare minskar det kortaste avståndet för någon nod, innebär det att en viss kant med negativ vikt har passerats en gång till. Det är viktigt att notera att under N-1 avslappningar, antog vi att varje vertex endast korsas en gång. Minskningen av avståndet under den N:e avslappningen indikerar dock att man återbesöker en vertex.

returnerar arrayer i java

Arbete med Bellman-Ford Algorithm för att detektera den negativa cykeln i grafen:

Låt oss anta att vi har en graf som ges nedan och vi vill ta reda på om det finns en negativ cykel eller inte med Bellman-Ford.

Inledande graf

Steg 1: Initiera en avståndsmatris Dist[] för att lagra det kortaste avståndet för varje vertex från källpunkten. Ursprungligen kommer avståndet till källan att vara 0 och avståndet till andra hörn kommer att vara Oändligt.

Initiera en distansmatris

Steg 2: Börja slappna av kanterna, under den första avslappningen:

  • Aktuellt avstånd till B> (Avstånd till A) + (vikt av A till B) dvs. oändlighet> 0 + 5
    • Därför är Dist[B] = 5

1:a avkoppling

rohit shetty skådespelare
Steg 3: Under den andra avslappningen:
  • Aktuellt avstånd till D> (avstånd till B) + (vikt av B till D) dvs. oändlighet> 5 + 2
    • Avstånd[D] = 7
  • Aktuellt avstånd till C> (avstånd till B) + (vikt av B till C) dvs. oändlighet> 5 + 1
    • Avstånd[C] = 6

2:a avkoppling

Steg 4: Under 3:e avslappningen:

  • Aktuellt avstånd till F> (avstånd till D ) + (vikt av D till F) d.v.s. oändlighet> 7 + 2
    • Avstånd[F] = 9
  • Aktuellt avstånd till E> (avstånd till C ) + (vikt av C till E) dvs. oändlighet> 6 + 1
    • Avstånd[E] = 7

3:e avkoppling

Steg 5: Under 4:e avkoppling:

  • Aktuellt avstånd till D> (avstånd till E) + (vikt av E till D) dvs. 7> 7 + (-1)
    • Avstånd[D] = 6
  • Aktuellt avstånd för E> (avstånd till F ) + (vikt av F till E) dvs. 7> 9 + (-3)
    • Avstånd[E] = 6

4:e avkoppling

Steg 6: Under 5:e avkoppling:

  • Aktuellt avstånd för F> (avstånd till D) + (vikt av D till F) dvs. 9> 6 + 2
    • Avstånd[F] = 8
  • Aktuellt avstånd till D> (avstånd till E ) + (vikt av E till D) dvs. 6> 6 + (-1)
    • Avstånd[D] = 5
  • Eftersom grafen h 6 hörn, Så under den 5:e relaxationen borde det kortaste avståndet för alla hörn ha beräknats.

5:e avkoppling

Steg 7: Nu bör den slutliga avslappningen, dvs. den 6:e avslappningen, indikera närvaron av negativ cykel om det finns några förändringar i avståndsfältet för 5:e avslappningen.

Under den sjätte avslappningen kan följande förändringar ses:

  • Aktuellt avstånd för E> (avstånd för F) + (vikt av F till E) dvs. 6> 8 + (-3)
    • Avstånd[E]=5
  • Aktuellt avstånd för F> (avstånd för D ) + (vikt av D till F) dvs. 8> 5 + 2
    • Avstånd[F]=7

Eftersom vi observerar förändringar i avståndsmatrisen. Därför kan vi dra slutsatsen att det finns en negativ cykel i grafen.

6:e avkoppling

java karta

Resultat: En negativ cykel (D->F->E) finns i grafen.

Algoritm för att hitta negativ cykel i en riktad viktad graf med hjälp av Bellman-Ford:

  • Initiera distansarray dist[] för varje vertex ' i ' som dist[v] = INFINITY .
  • Antag vilken vertex som helst (låt oss säga '0') som källa och tilldela dist = 0 .
  • Slappna av allt kanter (u,v,vikt) N-1 gånger enligt nedanstående villkor:
    • dist[v] = minimum(avstånd[v], avstånd[u] + vikt)
  • Slappna nu av alla kanter en gång till, dvs Nth tid och baserat på nedanstående två fall kan vi upptäcka den negativa cykeln:
    • Fall 1 (negativ cykel finns): För alla kant(u, v, vikt), om dist[u] + vikt
    • Fall 2 (ingen negativ cykel): fall 1 misslyckas för alla kanter.

Hantera frånkopplade grafer i algoritmen:

Ovanstående algoritm och program kanske inte fungerar om den givna grafen är frånkopplad. Det fungerar när alla hörn kan nås från källpunkten 0 .
För att hantera frånkopplade grafer kan vi upprepa ovanstående algoritm för hörn som har avstånd = OENDLIGHET, eller helt enkelt för de hörn som inte besöks.

Nedan är implementeringen av ovanstående tillvägagångssätt:

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 hörn, E-> Antal kanter int V, E;  // grafen representeras som en rad kanter.  struct Edge* edge; }; // Skapar en graf med V-hörn och 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];  returnera graf; } // En verktygsfunktion som används för att skriva ut lösningen void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  för (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];  // Steg 1: Initialisera avstånden från src till alla andra // hörn som OFINIT för (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->edge[j].src;  int v = graph->edge[j].dest;  int vikt = graf->kant[j].vikt;  if (avstånd[u] != INT_MAX && dist[u] + vikt< 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 = graph->edge[i].dest;  int vikt = graf->kant[i].vikt;  if (avstånd[u] != INT_MAX && dist[u] + vikt< 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->edge[0].src = 0;  graph->edge[0].dest = 1;  graf->kant[0].vikt = -1;  // lägg till kant 0-2 (eller A-C i ovanstående figur) graf->kant[1].src = 0;  graf->kant[1].dest = 2;  graf->kant[1].vikt = 4;  // lägg till kant 1-2 (eller B-C i ovanstående figur) graph->edge[2].src = 1;  graf->kant[2].dest = 2;  graf->kant[2].vikt = 3;  // lägg till kant 1-3 (eller B-D i ovanstående figur) graph->edge[3].src = 1;  graf->kant[3].dest = 3;  graf->kant[3].vikt = 2;  // lägg till kant 1-4 (eller B-E i ovanstående figur) graph->edge[4].src = 1;  graph->edge[4].dest = 4;  graf->kant[4].vikt = 2;  // lägg till kant 3-2 (eller D-C i ovanstående figur) graph->edge[5].src = 3;  graph->edge[5].dest = 2;  graf->kant[5].vikt = 5;  // lägg till kant 3-1 (eller D-B i ovanstående figur) graph->edge[6].src = 3;  graf->kant[6].dest = 1;  graf->kant[6].vikt = 1;  // lägg till kant 4-3 (eller E-D i ovanstående figur) graph->edge[7].src = 4;  graph->edge[7].dest = 3;  graf->kant[7].vikt = -3;    // Funktionsanrop BellmanFord(graf, 0);  returnera 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>

Komplexitetsanalys av Bellman-Fords algoritm :

  • Tidskomplexitet när grafen är ansluten:
    • Bästa fall: O(E), när avståndsuppsättningen efter 1:a och 2:a relaxation är samma, kan vi helt enkelt stoppa vidare bearbetning
    • Genomsnittligt fall: O(V*E)
    • Värsta fall: O(V*E)
  • Tidskomplexitet när grafen är frånkopplad :
    • Alla fall: O(E*(V^2))
  • Hjälputrymme: O(V), där V är antalet hörn i grafen.

Bellman Fords algoritmapplikationer:

  • Nätverksrouting: Bellman-Ford används i datornätverk för att hitta de kortaste vägarna i routingtabeller, vilket hjälper datapaket att navigera effektivt över nätverk.
  • GPS-navigering: GPS-enheter använder Bellman-Ford för att beräkna de kortaste eller snabbaste vägarna mellan platser, vilket underlättar navigeringsappar och -enheter.
  • Transport och logistik: Bellman-Fords algoritm kan användas för att bestämma de optimala vägarna för fordon inom transport och logistik, vilket minimerar bränsleförbrukning och restid.
  • Spelutveckling: Bellman-Ford kan användas för att modellera rörelse och navigering inom virtuella världar i spelutveckling, där olika vägar kan ha varierande kostnader eller hinder.
  • Robotik och autonoma fordon: Algoritmen hjälper till med vägplanering för robotar eller autonoma fordon, med hänsyn till hinder, terräng och energiförbrukning.

Nackdelen med Bellman Fords algoritm:

  • Bellman-Fords algoritm kommer att misslyckas om grafen innehåller någon negativ flankcykel.

Relaterade artiklar om enskild källas algoritmer för kortaste vägen: