logo

TechCodeview

Bellman-Fordův algoritmus

Představte si, že máte mapu s různými městy propojenými silnicemi, z nichž každá má určitou vzdálenost. The Algoritmus Bellman-Ford je jako průvodce, který vám pomůže najít nejkratší cestu z jednoho města do všech ostatních měst, i když některé silnice mají zápornou délku. Je to jako a GPS pro počítače, užitečné pro nalezení nejrychlejšího způsobu, jak se dostat z jednoho bodu do druhého v síti. V tomto článku se blíže podíváme na to, jak tento algoritmus funguje a proč je tak užitečný při řešení každodenních problémů.

Bellman-Fordův algoritmus

Obsah



Bellman-Fordův algoritmus

Bellman-Ford je jediný zdroj algoritmus nejkratší cesty, který určuje nejkratší cestu mezi daným zdrojovým vrcholem a každým dalším vrcholem v grafu. Tento algoritmus lze použít na obou vážený a nevážený grafy.

java datum nyní

A Bellman-Ford Algoritmus také zaručeně najde nejkratší cestu v grafu, podobně jako Dijkstrův algoritmus . I když Bellman-Ford je pomalejší než Dijkstrův algoritmus , je schopen pracovat s grafy záporné závaží hran , díky čemuž je všestrannější. Nejkratší cestu nelze najít, pokud existuje a negativní cyklus v grafu. Pokud budeme i nadále obcházet negativní cyklus nekonečněkrát, pak náklady na cestu budou nadále klesat (i když se délka cesty prodlužuje). Jako výsledek, Bellman-Ford je také schopen detekovat negativní cykly , což je důležitá vlastnost.

Myšlenka algoritmu Bellman Ford:

Primárním principem Bellman-Fordova algoritmu je, že začíná s jediným zdrojem a vypočítává vzdálenost ke každému uzlu. Vzdálenost je zpočátku neznámá a předpokládá se, že je nekonečná, ale jak čas plyne, algoritmus tyto cesty uvolňuje tím, že identifikuje několik kratších cest. Proto se říká, že Bellman-Ford je založen na Princip relaxace .

Princip relaxace hran pro Bellman-Ford:

  • Uvádí, že pro graf má N vrcholy, všechny hrany by měly být uvolněné N-1 časů pro výpočet nejkratší cesty z jednoho zdroje.
  • Abychom zjistili, zda existuje záporný cyklus, nebo ne, uvolněte celou hranu ještě jednou a pokud se nejkratší vzdálenost pro kterýkoli uzel zmenší, můžeme říci, že existuje záporný cyklus. Zkrátka pokud uvolníme okraje N časy a existuje jakákoli změna v nejkratší vzdálenosti jakéhokoli uzlu mezi N-1st a Nth relaxace než negativní cyklus existuje, jinak neexistuje.

Proč Relaxing Edges N-1 krát, nám dává jeden zdroj nejkratší cestu?

V nejhorším případě může mít nejkratší cestu mezi dvěma vrcholy nejvýše N-1 hrany, kde N je počet vrcholů. Je to proto, že jednoduchá cesta v grafu s N vrcholy mohou mít max N-1 hrany, protože je nemožné vytvořit uzavřenou smyčku bez přehodnocení vrcholu.

Uvolněním okrajů N-1 Algoritmus Bellman-Ford zajišťuje, že odhady vzdálenosti pro všechny vrcholy byly aktualizovány na optimální hodnoty, za předpokladu, že graf neobsahuje žádné cykly se zápornou váhou dosažitelné ze zdrojového vrcholu. Pokud graf obsahuje cyklus záporné váhy dosažitelný ze zdrojového vrcholu, algoritmus jej může detekovat po N-1 iterací, protože negativní cyklus narušuje nejkratší délky cesty.

Stručně řečeno, relaxační hrany N-1 časy v algoritmu Bellman-Ford zaručuje, že algoritmus prozkoumal všechny možné cesty délky až N-1 , což je maximální možná délka nejkratší cesty v grafu s N vrcholy. To umožňuje algoritmu správně vypočítat nejkratší cesty ze zdrojového vrcholu do všech ostatních vrcholů, za předpokladu, že neexistují žádné cykly se zápornou váhou.

gimp uložit jako jpeg

Proč zmenšování vzdálenosti v N'-té relaxaci ukazuje na existenci negativního cyklu?

Jak bylo diskutováno dříve, dosažení nejkratších cest z jediného zdroje ke všem ostatním uzlům vyžaduje N-1 relaxace. Pokud N’-tá relaxace dále snižuje nejkratší vzdálenost pro jakýkoli uzel, znamená to, že určitá hrana se zápornou váhou byla znovu překročena. Je důležité si uvědomit, že během N-1 relaxací, předpokládali jsme, že každý vrchol se projde pouze jednou. Snížení vzdálenosti během N'-té relaxace však ukazuje na přehodnocení vrcholu.

Fungování Bellman-Fordova algoritmu pro detekci negativního cyklu v grafu:

Předpokládejme, že máme graf, který je uveden níže, a pomocí Bellman-Ford chceme zjistit, zda existuje negativní cyklus nebo ne.

Počáteční graf

Krok 1: Inicializujte pole vzdálenosti Dist[] pro uložení nejkratší vzdálenosti pro každý vrchol od zdrojového vrcholu. Zpočátku bude vzdálenost zdroje 0 a vzdálenost ostatních vrcholů bude NEKONEČNO.

Inicializujte pole vzdálenosti

Krok 2: Začněte uvolňovat okraje během 1. relaxace:

  • Aktuální vzdálenost B> (Vzdálenost A) + (Hmotnost A až B) tj. nekonečno> 0 + 5
    • Proto Dist[B] = 5

1. Relaxace

Krok 3: Během 2. relaxace:
  • Aktuální vzdálenost D> (vzdálenost B) + (hmotnost B až D), tj. nekonečno> 5 + 2
    • Vzdálenost[D] = 7
  • Aktuální vzdálenost C> (Vzdálenost B) + (Hmotnost B až C) tj. nekonečno> 5 + 1
    • Vzdálenost [C] = 6

2. Relaxace

Krok 4: Během 3. relaxace:

panda pivot
  • Aktuální vzdálenost F> (Vzdálenost D ) + (Hmotnost D až F) tj. nekonečno> 7 + 2
    • Vzdálenost[F] = 9
  • Aktuální vzdálenost E> (Vzdálenost C ) + (Hmotnost C až E) tj. nekonečno> 6 + 1
    • Vzdálenost[E] = 7

3. Relaxace

Krok 5: Během 4. relaxace:

  • Aktuální vzdálenost D> (Vzdálenost E) + (Hmotnost E k D) tj. 7> 7 + (-1)
    • Vzdálenost[D] = 6
  • Aktuální vzdálenost E> (Vzdálenost F ) + (Hmotnost F až E) tj. 7> 9 + (-3)
    • Vzdálenost[E] = 6

4. Relaxace

Krok 6: Během páté relaxace:

  • Aktuální vzdálenost F> (Vzdálenost D) + (Hmotnost D až F) tj. 9> 6 + 2
    • Vzdálenost[F] = 8
  • Aktuální vzdálenost D> (Vzdálenost E ) + (Hmotnost E k D) tj. 6> 6 + (-1)
    • Vzdálenost[D] = 5
  • Vzhledem k tomu, že graf h 6 vrcholů, tak během 5. relaxace měla být vypočtena nejkratší vzdálenost pro všechny vrcholy.

5. Relaxace

Krok 7: Nyní by konečná relaxace, tj. 6. relaxace, měla indikovat přítomnost negativního cyklu, pokud dojde k nějakým změnám v poli vzdáleností 5. relaxace.

Během 6. relaxace lze pozorovat následující změny:

  • Aktuální vzdálenost E> (Vzdálenost F) + (Hmotnost F až E) tj. 6> 8 + (-3)
    • Dist[E]=5
  • Aktuální vzdálenost F> (Vzdálenost D ) + (Hmotnost D až F) tj. 8> 5 + 2
    • Dist[F]=7

Protože pozorujeme změny v poli Distance, můžeme usuzovat na přítomnost negativního cyklu v grafu.

6. Relaxace

nekonečná smyčka

Výsledek: V grafu existuje negativní cyklus (D->F->E).

Algoritmus k nalezení negativního cyklu v řízeném váženém grafu pomocí Bellman-Ford:

  • Inicializujte vzdálenost pole dist[] pro každý vrchol ‘ v ' tak jako dist[v] = NEKONEČNO .
  • Předpokládejme jakýkoli vrchol (řekněme „0“) jako zdroj a přiřaďte jej vzdálenost = 0 .
  • Uvolněte se všechny hrany(u,v,hmotnost) N-1 časy podle níže uvedené podmínky:
    • dist[v] = minimum(vzdálenost[v], vzdálenost[u] + hmotnost)
  • Nyní uvolněte všechny okraje ještě jednou, tj Nth čas a na základě níže uvedených dvou případů můžeme detekovat negativní cyklus:
    • Případ 1 (existuje negativní cyklus): Pro všechny edge(u, v, weight), if dist[u] + weight
    • Případ 2 (žádný záporný cyklus): případ 1 selže pro všechny hrany.

Zpracování odpojených grafů v algoritmu:

Výše uvedený algoritmus a program nemusí fungovat, pokud je daný graf odpojen. Funguje, když jsou všechny vertexy dosažitelné ze zdrojového vertexu 0 .
Abychom zvládli nespojené grafy, můžeme zopakovat výše uvedený algoritmus pro vrcholy, které mají vzdálenost = NEKONEČNO, nebo jednoduše pro vrcholy, které nejsou navštěvovány.

Níže je uvedena implementace výše uvedeného přístupu:

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->Počet vrcholů, E-> Počet hran int V, E;  // graf je reprezentován jako pole hran.  struct Hrana* hrana; }; // Vytvoří graf s V vrcholy a E hranami struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  graf->V = V;  graf->E = E;  graf->hrana = nová Hrana[E];  návratový graf; } // Obslužná funkce používaná k vytištění řešení void printArr(int dist[], int n) { printf('Vzdálenost vrcholu od zdroje
');  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->PROTI;  int E = graf->E;  int dist[V];  // Krok 1: Inicializujte vzdálenosti od src ke všem ostatním // vrcholům jako NEKONEČNÉ pro (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->hrana[j].src;  int v = graf->hrana[j].dest;  int váha = graf->hrana[j].váha;  if (vzdálenost[u] != INT_MAX && dist[u] + hmotnost< 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->hrana[i].src;  int v = graf->hrana[i].dest;  int váha = graf->hrana[i].váha;  if (vzdálenost[u] != INT_MAX && dist[u] + hmotnost< 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->hrana[0].src = 0;  graf->hrana[0].dest = 1;  graf->hrana[0].váha = -1;  // přidání hrany 0-2 (nebo A-C na obrázku výše) graph->edge[1].src = 0;  graf->hrana[1].dest = 2;  graf->hrana[1].váha = 4;  // přidání hrany 1-2 (nebo B-C na obrázku výše) graph->edge[2].src = 1;  graf->hrana[2].dest = 2;  graf->hrana[2].váha = 3;  // přidání hrany 1-3 (nebo B-D na obrázku výše) graph->edge[3].src = 1;  graf->hrana[3].dest = 3;  graf->hrana[3].váha = 2;  // přidání hrany 1-4 (nebo B-E na obrázku výše) graph->edge[4].src = 1;  graf->hrana[4].dest = 4;  graf->hrana[4].váha = 2;  // přidání hrany 3-2 (nebo D-C na obrázku výše) graph->edge[5].src = 3;  graf->hrana[5].dest = 2;  graf->hrana[5].váha = 5;  // přidání hrany 3-1 (nebo D-B na obrázku výše) graph->edge[6].src = 3;  graf->hrana[6].dest = 1;  graf->hrana[6].váha = 1;  // přidání hrany 4-3 (nebo E-D na obrázku výše) graph->edge[7].src = 4;  graf->hrana[7].dest = 3;  graf->hrana[7].váha = -3;    // Volání funkce BellmanFord(graph, 0);  návrat 0; }>
Jáva 
// 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);>
Výstup 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Analýza složitosti Bellman-Fordova algoritmu :

  • Časová složitost při připojení grafu:
    • Nejlepší případ: O(E), když je pole vzdáleností po 1. a 2. relaxaci stejné, můžeme jednoduše zastavit další zpracování
    • Průměrný případ: O(V*E)
    • Nejhorší případ: O(V*E)
  • Časová složitost při odpojeném grafu :
    • Všechny případy: O(E*(V^2))
  • Pomocný prostor: O(V), kde V je počet vrcholů v grafu.

Aplikace algoritmu Bellmana Forda:

  • Směrování sítě: Bellman-Ford se používá v počítačových sítích k nalezení nejkratších cest ve směrovacích tabulkách, což pomáhá datovým paketům efektivně procházet sítěmi.
  • GPS Navigace: Zařízení GPS používají Bellman-Ford k výpočtu nejkratších nebo nejrychlejších tras mezi místy, což pomáhá navigačním aplikacím a zařízením.
  • Doprava a logistika: Algoritmus společnosti Bellman-Ford lze použít k určení optimálních cest pro vozidla v dopravě a logistice, čímž se minimalizuje spotřeba paliva a doba jízdy.
  • Vývoj hry: Bellman-Ford lze použít k modelování pohybu a navigace ve virtuálních světech při vývoji her, kde různé cesty mohou mít různé náklady nebo překážky.
  • Robotika a autonomní vozidla: Algoritmus pomáhá při plánování cesty pro roboty nebo autonomní vozidla s ohledem na překážky, terén a spotřebu energie.

Nevýhoda algoritmu Bellmana Forda:

  • Bellman-Fordův algoritmus selže, pokud graf obsahuje jakýkoli cyklus záporné hrany.

Související články o algoritmech nejkratší cesty z jednoho zdroje: