logo

TechCodeview

Bellman-Ford algoritms

Iedomājieties, ka jums ir karte ar dažādām pilsētām, kuras savieno ceļi, un katram ceļam ir noteikts attālums. The Belmana-Forda algoritms ir kā ceļvedis, kas palīdz atrast īsāko ceļu no vienas pilsētas uz citām pilsētām, pat ja dažiem ceļiem ir negatīvs garums. Tas ir kā a GPS datoriem — noder, lai noskaidrotu ātrāko veidu, kā tīklā nokļūt no viena punkta uz otru. Šajā rakstā mēs sīkāk aplūkosim, kā šis algoritms darbojas un kāpēc tas ir tik ērts ikdienas problēmu risināšanā.

Bellman-Ford-algoritms

Satura rādītājs



Bellman-Ford algoritms

Bellman-Ford ir viens avots Īsākā ceļa algoritms, kas nosaka īsāko ceļu starp doto avota virsotni un katru otro virsotni grafā. Šo algoritmu var izmantot abos gadījumos svērtais un nesvērts grafiki.

diskrētās matemātikas noliegums

A Bellman-Ford algoritms ir arī garantēts, lai atrastu īsāko ceļu grafikā, līdzīgi kā Dijkstras algoritms . Lai gan Bellman-Ford ir lēnāks nekā Dijkstras algoritms , tas spēj apstrādāt grafikus ar negatīvie malu atsvari , kas padara to daudzpusīgāku. Īsāko ceļu nevar atrast, ja pastāv a negatīvs cikls grafikā. Ja turpināsim apiet negatīvo ciklu bezgalīgi daudz reižu, tad ceļa izmaksas turpinās samazināties (lai gan ceļa garums palielinās). Rezultātā, Bellman-Ford spēj arī atklāt negatīvie cikli , kas ir svarīga funkcija.

Bellman Ford algoritma ideja:

Bellman-Ford algoritma galvenais princips ir tāds, ka tas sākas ar vienu avotu un aprēķina attālumu līdz katram mezglam. Sākotnēji attālums nav zināms un tiek pieņemts kā bezgalīgs, taču, laikam ejot, algoritms šos ceļus atvieglo, nosakot dažus īsākus ceļus. Tāpēc tiek teikts, ka Bellman-Ford pamatā ir Relaksācijas princips .

Malu atslābināšanas princips automašīnai Bellman-Ford:

  • Tajā teikts, ka grafikam, kam N virsotnēm, visām malām jābūt atslābinātām N-1 reizes, lai aprēķinātu viena avota īsāko ceļu.
  • Lai noteiktu, vai negatīvs cikls pastāv vai nē, atslābiniet visu malu vēlreiz un, ja jebkura mezgla īsākais attālums samazinās, mēs varam teikt, ka pastāv negatīvs cikls. Īsāk sakot, ja mēs atslābinām malas N reizes, un ir kādas izmaiņas jebkura mezgla īsākajā attālumā starp N-1 un Nth relaksācija nekā negatīvs cikls pastāv, citādi neeksistē.

Kāpēc Relaxing Edges N-1 reizes sniedz mums viena avota īsāko ceļu?

Sliktākajā gadījumā var būt īsākais ceļš starp divām virsotnēm N-1 malas, kur N ir virsotņu skaits. Tas ir tāpēc, ka vienkāršs ceļš grafikā ar N virsotnēm var būt ne vairāk kā N-1 malas, jo nav iespējams izveidot slēgtu cilpu, atkārtoti neapmeklējot virsotni.

Atslābinot malas N-1 reizes, Bellman-Ford algoritms nodrošina, ka attāluma aprēķini visām virsotnēm ir atjaunināti līdz to optimālajām vērtībām, pieņemot, ka grafikā nav negatīva svara ciklu, kas ir sasniedzami no avota virsotnes. Ja grafikā ir negatīva svara cikls, kas sasniedzams no avota virsotnes, algoritms to var noteikt pēc N-1 iterācijas, jo negatīvais cikls izjauc īsākos ceļa garumus.

Rezumējot, relaksējošas malas N-1 reizes Bellman-Ford algoritmā garantē, ka algoritms ir izpētījis visus iespējamos garuma ceļus līdz pat N-1 , kas ir maksimālais iespējamais īsākā ceļa garums grafikā ar N virsotnes. Tas ļauj algoritmam pareizi aprēķināt īsākos ceļus no avota virsotnes uz visām pārējām virsotnēm, ņemot vērā, ka nav negatīva svara ciklu.

Kāpēc attāluma samazināšana N relaksācijā norāda uz negatīva cikla esamību?

Kā jau iepriekš tika apspriests, viena avota sasniegšanai ir nepieciešami īsākie ceļi uz visiem pārējiem mezgliem N-1 relaksācijas. Ja N relaksācija vēl vairāk samazina jebkura mezgla īsāko attālumu, tas nozīmē, ka noteikta mala ar negatīvu svaru ir šķērsota vēlreiz. Ir svarīgi atzīmēt, ka laikā N-1 relaksācijas, mēs pieņēmām, ka katra virsotne tiek šķērsota tikai vienu reizi. Tomēr attāluma samazināšana N relaksācijas laikā norāda uz virsotnes atkārtotu apmeklēšanu.

Bellman-Ford algoritma darbība, lai grafikā noteiktu negatīvo ciklu:

Pieņemsim, ka mums ir grafiks, kas ir parādīts zemāk, un mēs vēlamies noskaidrot, vai pastāv negatīvs cikls vai neizmantojot Bellman-Ford.

Sākotnējais grafiks

1. darbība: Inicializējiet attāluma masīvu Dist[], lai saglabātu katras virsotnes īsāko attālumu no avota virsotnes. Sākotnēji avota attālums būs 0 un attālums no pārējām virsotnēm būs BEZGALĪBA.

python generē uuid

Inicializējiet attāluma masīvu

2. darbība: Sāciet atslābināt malas 1. relaksācijas laikā:

  • Pašreizējais attālums no B> (attālums no A) + (no A līdz B svars), t.i., bezgalība> 0 + 5
    • Tāpēc Dist[B] = 5

1. Relaksācija

3. darbība: Otrās relaksācijas laikā:
  • Pašreizējais attālums no D> (attālums no B) + (no B līdz D svars), t.i., bezgalība> 5 + 2
    • Dist[D] = 7
  • Pašreizējais attālums no C> (attālums no B) + (no B līdz C svars), t.i., bezgalība> 5 + 1
    • Dist[C] = 6

2. Relaksācija

vlc multivides atskaņotāja lejupielāde youtube

4. darbība: Trešās relaksācijas laikā:

  • Pašreizējais attālums no F> (attālums no D ) + (no D līdz F svars), t.i., bezgalība> 7 + 2
    • Dist[F] = 9
  • Pašreizējais attālums no E> (attālums no C ) + (no C līdz E svars), t.i., bezgalība> 6 + 1
    • Dist[E] = 7

3. Relaksācija

5. darbība: Ceturtās relaksācijas laikā:

  • Pašreizējais attālums no D> (attālums no E) + (no E līdz D svars), t.i., 7> 7 + (-1)
    • Dist[D] = 6
  • Pašreizējais attālums no E> (attālums no F ) + (F līdz E svars), t.i., 7> 9 + (-3)
    • Dist[E] = 6

4. Relaksācija

6. darbība: 5. relaksācijas laikā:

  • Pašreizējais attālums no F> (attālums no D) + (no D līdz F svars), t.i., 9> 6 + 2
    • Dist[F] = 8
  • Pašreizējais attālums no D> (attālums no E ) + (no E līdz D svars), t.i., 6> 6 + (-1)
    • Dist[D] = 5
  • Tā kā grafam h 6 virsotnes, Tātad 5. relaksācijas laikā vajadzēja aprēķināt īsāko attālumu visām virsotnēm.

5. Relaksācija

7. darbība: Tagad galīgajai relaksācijai, t.i., 6. relaksācijai, vajadzētu norādīt uz negatīva cikla klātbūtni, ja ir kādas izmaiņas 5. relaksācijas attāluma masīvā.

6. relaksācijas laikā var novērot šādas izmaiņas:

  • Pašreizējais attālums no E> (attālums no F) + (no F līdz E svars), t.i., 6> 8 + (-3)
    • Dist[E]=5
  • Pašreizējais attālums no F> (attālums no D ) + (no D līdz F svars), t.i., 8> 5 + 2
    • Dist[F]=7

Tā kā mēs novērojam izmaiņas attāluma masīvā, mēs varam secināt, ka grafikā ir negatīvs cikls.

6. Relaksācija

java virkne satur

Rezultāts: Grafikā pastāv negatīvs cikls (D->F->E).

Algoritms negatīva cikla atrašanai virzītā svērtā diagrammā, izmantojot Bellman-Ford:

  • Inicializēt attāluma masīvu dist[] katrai virsotnei ' iekšā ‘kā dist[v] = BEZGALĪBA .
  • Pieņemsim jebkuru virsotni (teiksim “0”) kā avotu un piešķiriet dist = 0 .
  • Atpūtieties visi malas(u,v,svars) N-1 reizes saskaņā ar tālāk norādīto nosacījumu:
    • attālums[v] = minimums (attālums[v], attālums [u] + svars)
  • Tagad vēl vienu reizi atslābiniet visas malas, t.i Nth laikā un, pamatojoties uz tālāk norādītajiem diviem gadījumiem, mēs varam noteikt negatīvo ciklu:
    • 1. gadījums (pastāv negatīvs cikls): jebkuram mala(u, v, svars), ja dist[u] + svars
    • 2. gadījums (nav negatīva cikla): 1. gadījums neizdodas visām malām.

Atvienotu grafiku apstrāde algoritmā:

Iepriekš minētais algoritms un programma var nedarboties, ja dotais grafiks ir atvienots. Tas darbojas, ja visas virsotnes ir sasniedzamas no avota virsotnes 0 .
Lai apstrādātu atvienotus grafikus, mēs varam atkārtot iepriekš minēto algoritmu virsotnēm, kurām ir attālums = BEZGALĪBA, vai vienkārši virsotnēm, kuras netiek apmeklētas.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

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->Virsotņu skaits, E-> Malu skaits int V, E;  // grafiks tiek attēlots kā malu masīvs.  struct Edge* mala; }; // Izveido grafiku ar V virsotnēm un E malām struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  grafiks->V = V;  grafiks->E = E;  grafiks->mala = jauna mala[E];  atgriešanās grafiks; } // Lietderības funkcija, ko izmanto risinājuma drukāšanai 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 = grafiks->E;  int dist[V];  // 1. darbība. Inicializējiet attālumus no src līdz visām pārējām // virsotnēm kā BEIGAS, ja (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->mala[j].src;  int v = grafiks->mala[j].dest;  int svars = grafiks->mala[j].svars;  if (dist[u] != INT_MAX && dist[u] + svars< 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->mala[i].src;  int v = grafiks->mala[i].dest;  int svars = grafiks->mala[i].svars;  if (dist[u] != INT_MAX && dist[u] + svars< 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->mala[0].src = 0;  graph->edge[0].dest = 1;  grafiks->mala[0].svars = -1;  // pievienot malu 0-2 (vai A-C augstāk attēlā) graph->edge[1].src = 0;  graph->edge[1].dest = 2;  grafiks->mala[1].svars = 4;  // pievienot malu 1-2 (vai B-C augstāk redzamajā attēlā) graph->edge[2].src = 1;  graph->edge[2].dest = 2;  grafiks->mala[2].svars = 3;  // pievienot malu 1-3 (vai B-D iepriekš attēlā) graph->edge[3].src = 1;  graph->edge[3].dest = 3;  grafiks->mala[3].svars = 2;  // pievienot malu 1-4 (vai B-E iepriekš attēlā) graph->edge[4].src = 1;  grafiks->mala[4].dest = 4;  grafiks->mala[4].svars = 2;  // pievienot malu 3-2 (vai D-C augstāk attēlā) graph->edge[5].src = 3;  grafiks->mala[5].dest = 2;  grafiks->mala[5].svars = 5;  // pievienot malu 3-1 (vai D-B augstākajā attēlā) graph->edge[6].src = 3;  graph->edge[6].dest = 1;  grafiks->mala[6].svars = 1;  // pievienot malu 4-3 (vai E-D augstāk attēlā) graph->edge[7].src = 4;  graph->edge[7].dest = 3;  grafiks->mala[7].svars = -3;    // Funkcijas izsaukums BellmanFord(graph, 0);  atgriezties 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);>
Izvade 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Bellman-Ford algoritma sarežģītības analīze :

  • Laika sarežģītība, kad grafiks ir savienots:
    • Labākais gadījums: O(E), ja attāluma masīvs pēc 1. un 2. relaksācijas ir vienāds, mēs varam vienkārši pārtraukt turpmāko apstrādi
    • Vidējais gadījums: O(V*E)
    • Sliktākajā gadījumā: O(V*E)
  • Laika sarežģītība, kad grafiks ir atvienots :
    • Visi gadījumi: O(E*(V^2))
  • Palīgtelpa: O(V), kur V ir grafa virsotņu skaits.

Bellman Ford algoritmu lietojumprogrammas:

  • Tīkla maršrutēšana: Bellman-Ford tiek izmantots datortīklos, lai maršrutēšanas tabulās atrastu īsākos ceļus, palīdzot datu paketēm efektīvi pārvietoties pa tīkliem.
  • GPS navigācija: GPS ierīces izmanto Bellman-Ford, lai aprēķinātu īsākos vai ātrākos maršrutus starp vietām, palīdzot navigācijas programmām un ierīcēm.
  • Transports un loģistika: Bellman-Ford algoritmu var izmantot, lai noteiktu optimālos ceļus transportlīdzekļiem transportā un loģistikā, samazinot degvielas patēriņu un brauciena laiku.
  • Spēļu izstrāde: Bellman-Ford var izmantot, lai modelētu kustību un navigāciju virtuālās pasaulēs spēļu izstrādē, kur dažādiem ceļiem var būt dažādas izmaksas vai šķēršļi.
  • Robotika un autonomie transportlīdzekļi: Algoritms palīdz robotu vai autonomo transportlīdzekļu ceļa plānošanā, ņemot vērā šķēršļus, reljefu un enerģijas patēriņu.

Belmana Forda algoritma trūkums:

  • Bellman-Ford algoritms neizdosies, ja grafikā ir kāds negatīvs malu cikls.

Saistītie raksti par viena avota īsākā ceļa algoritmiem: