logo

TechCodeview

Algoritmo di Bellman-Ford

Immagina di avere una mappa con diverse città collegate da strade, ciascuna strada avente una certa distanza. IL Algoritmo di Bellman-Ford è come una guida che ti aiuta a trovare il percorso più breve da una città a tutte le altre città, anche se alcune strade hanno lunghezze negative. È come un GPS per i computer, utile per individuare il modo più rapido per spostarsi da un punto all'altro di una rete. In questo articolo daremo uno sguardo più da vicino a come funziona questo algoritmo e perché è così utile per risolvere i problemi quotidiani.

Algoritmo di Bellman-Ford

Tabella dei contenuti



Algoritmo di Bellman-Ford

Bellman-Ford è un unica fonte algoritmo del percorso più breve che determina il percorso più breve tra un dato vertice sorgente e ogni altro vertice in un grafico. Questo algoritmo può essere utilizzato su entrambi ponderato E non ponderato grafici.

Linux Mint Cannella vs Mate

UN Bellman-Ford è inoltre garantito che l'algoritmo trovi il percorso più breve in un grafico, simile a Algoritmo di Dijkstra . Sebbene Bellman-Ford sia più lento di Algoritmo di Dijkstra , è in grado di gestire grafici con pesi dei fronti negativi , il che lo rende più versatile. Non è possibile trovare il percorso più breve se esiste a ciclo negativo nel grafico. Se continuiamo a percorrere il ciclo negativo un numero infinito di volte, il costo del percorso continuerà a diminuire (anche se la lunghezza del percorso aumenta). Di conseguenza, Bellman-Ford è anche in grado di rilevare cicli negativi , che è una caratteristica importante.

L’idea alla base dell’algoritmo Bellman Ford:

Il principio fondamentale dell’algoritmo Bellman-Ford è che inizia con una singola sorgente e calcola la distanza da ciascun nodo. La distanza è inizialmente sconosciuta e si presume infinita, ma col passare del tempo l'algoritmo allenta questi percorsi identificando alcuni percorsi più brevi. Quindi si dice che Bellman-Ford sia basato su Principio di rilassamento .

Principio di rilassamento dei bordi per Bellman-Ford:

  • Si afferma che per il grafico avente N vertici, tutti i bordi dovrebbero essere rilassati N-1 volte per calcolare il percorso più breve della singola sorgente.
  • Per rilevare se esiste o meno un ciclo negativo, rilassare ancora una volta tutti i bordi e se la distanza più breve per qualsiasi nodo si riduce allora possiamo dire che esiste un ciclo negativo. Insomma se rilassiamo i bordi N volte, e vi è alcun cambiamento nella distanza più breve di qualsiasi nodo tra i N-1 E L'ennesimo rilassamento rispetto ad un ciclo negativo che esiste, altrimenti non esiste.

Perché Relaxing Edges N-1 volte ci fornisce il percorso più breve a sorgente singola?

Nel peggiore dei casi, il percorso più breve tra due vertici può avere al massimo N-1 bordi, dove N è il numero di vertici. Questo perché un percorso semplice in un grafico con N i vertici possono avere al massimo N-1 bordi, poiché è impossibile formare un anello chiuso senza rivisitare un vertice.

Rilassando i bordi N-1 volte, l'algoritmo Bellman-Ford garantisce che le stime della distanza per tutti i vertici siano state aggiornate ai loro valori ottimali, presupponendo che il grafico non contenga cicli di peso negativo raggiungibili dal vertice sorgente. Se un grafico contiene un ciclo di peso negativo raggiungibile dal vertice sorgente, l'algoritmo può rilevarlo successivamente N-1 iterazioni, poiché il ciclo negativo interrompe le lunghezze del percorso più breve.

In sintesi, bordi rilassanti N-1 volte nell'algoritmo Bellman-Ford garantisce che l'algoritmo abbia esplorato tutti i possibili percorsi di lunghezza fino a N-1 , che è la lunghezza massima possibile di un percorso più breve in un grafico con N vertici. Ciò consente all'algoritmo di calcolare correttamente i percorsi più brevi dal vertice sorgente a tutti gli altri vertici, dato che non esistono cicli di peso negativo.

pseudocodice Java

Perché la riduzione della distanza nell’ennesimo rilassamento indica l’esistenza di un ciclo negativo?

Come discusso in precedenza, è necessario ottenere i percorsi più brevi da un'unica fonte verso tutti gli altri nodi N-1 rilassamenti. Se l’N-esimo rilassamento riduce ulteriormente la distanza più breve per qualsiasi nodo, ciò implica che un certo bordo con peso negativo è stato attraversato ancora una volta. È importante notare che durante il N-1 rilassamenti, abbiamo supposto che ciascun vertice venga attraversato una sola volta. Tuttavia, la riduzione della distanza durante l’ennesimo rilassamento indica la rivisitazione di un vertice.

Funzionamento dell'algoritmo Bellman-Ford per rilevare il ciclo negativo nel grafico:

Supponiamo di avere un grafico riportato di seguito e di voler scoprire se esiste o meno un ciclo negativo utilizzando Bellman-Ford.

Grafico iniziale

Passo 1: Inizializza un array di distanze Dist[] per memorizzare la distanza più breve per ciascun vertice dal vertice di origine. Inizialmente la distanza della sorgente sarà 0 e la distanza degli altri vertici sarà INFINITO.

Inizializza un array di distanze

Passo 2: Iniziare a rilassare i bordi, durante il 1° Rilassamento:

  • Distanza attuale di B> (Distanza di A) + (Peso di A a B) cioè Infinito> 0 + 5
    • Pertanto, Dist[B] = 5

1° Rilassamento

Passaggio 3: Durante il 2° Rilassamento:
  • Distanza attuale di D> (Distanza di B) + (Peso di B a D) cioè Infinito> 5 + 2
    • Dist[D] = 7
  • Distanza attuale di C> (Distanza di B) + (Peso di B rispetto a C) ovvero Infinito> 5 + 1
    • Dist[C] = 6

2° Rilassamento

Passaggio 4: Durante il 3° Rilassamento:

strati del modello osi
  • Distanza attuale di F> (Distanza di D ) + (Peso di D a F) cioè Infinito> 7 + 2
    • Dist[F] = 9
  • Distanza attuale di E> (Distanza di C ) + (Peso di C rispetto a E) ovvero Infinito> 6 + 1
    • Dist[E] = 7

3° Rilassamento

Passaggio 5: Durante il 4° Rilassamento:

  • Distanza attuale di D> (Distanza di E) + (Peso di E a D) ovvero 7> 7 + (-1)
    • Dist[D] = 6
  • Distanza attuale di E> (Distanza di F ) + (Peso di F rispetto a E) ovvero 7> 9 + (-3)
    • Dist[E] = 6

4° Rilassamento

Passaggio 6: Durante il 5° Rilassamento:

  • Distanza attuale di F> (Distanza di D) + (Peso di D a F) ovvero 9> 6 + 2
    • Dist[F] = 8
  • Distanza attuale di D> (Distanza di E ) + (Peso di E rispetto a D) ovvero 6> 6 + (-1)
    • Dist[D] = 5
  • Poiché il grafico h 6 vertici, quindi durante il 5° rilassamento si sarebbe dovuta calcolare la distanza più breve per tutti i vertici.

5° Rilassamento

Passaggio 7: Ora il rilassamento finale, cioè il 6° rilassamento, dovrebbe indicare la presenza di un ciclo negativo se ci sono cambiamenti nella matrice di distanza del 5° rilassamento.

Durante il 6° rilassamento si possono osservare i seguenti cambiamenti:

  • Distanza attuale di E> (Distanza di F) + (Peso di F rispetto a E) ovvero 6> 8 + (-3)
    • Dist[E]=5
  • Distanza attuale di F> (Distanza di D ) + (Peso di D a F) ovvero 8> 5 + 2
    • Dist[F]=7

Poiché osserviamo i cambiamenti nell'array Distance, possiamo concludere la presenza di un ciclo negativo nel grafico.

6° Rilassamento

PD unire

Risultato: Nel grafico esiste un ciclo negativo (D->F->E).

Algoritmo per trovare il ciclo negativo in un grafico ponderato diretto utilizzando Bellman-Ford:

  • Inizializza l'array di distanza dist[] per ogni vertice ' In ' COME dist[v] = INFINITO .
  • Assumi qualsiasi vertice (diciamo '0') come sorgente e assegna dist = 0 .
  • Rilassati tutto bordi(u,v,peso) N-1 volte secondo la condizione seguente:
    • dist[v] = minimo(dist[v], distanza[u] + peso)
  • Ora rilassa tutti i bordi ancora una volta, ad esempio il L'ennesimo tempo e in base ai due casi seguenti possiamo rilevare il ciclo negativo:
    • Caso 1 (Esiste un ciclo negativo): Per qualsiasi bordo(u, v, peso), se dist[u] + peso
    • Caso 2 (Nessun ciclo negativo): il caso 1 fallisce per tutti i bordi.

Gestire i grafici disconnessi nell'algoritmo:

L'algoritmo e il programma di cui sopra potrebbero non funzionare se il grafico fornito è disconnesso. Funziona quando tutti i vertici sono raggiungibili dal vertice di origine 0 .
Per gestire i grafici disconnessi, possiamo ripetere l'algoritmo precedente per i vertici che hanno distanza = INFINITO, o semplicemente per i vertici che non vengono visitati.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

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->Numero di vertici, E-> Numero di spigoli int V, E;  // il grafico è rappresentato come un array di spigoli.  struttura Bordo* bordo; }; // Crea un grafico con vertici V e bordi E struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  grafico->V = V;  grafico->E = E;  grafico->spigolo = nuovo Spigolo[E];  grafico di ritorno; } // Una funzione di utilità utilizzata per stampare la soluzione 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 = grafico->E;  int dist[V];  // Passo 1: Inizializza le distanze da src a tutti gli altri // vertici come INFINITI per (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->bordo[j].src;  int v = grafico->bordo[j].dest;  int peso = grafico->bordo[j].peso;  if (dist[u] != INT_MAX && dist[u] + peso< 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->bordo[i].src;  int v = grafico->bordo[i].dest;  int peso = grafico->bordo[i].peso;  if (dist[u] != INT_MAX && dist[u] + peso< 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->bordo[0].src = 0;  grafico->bordo[0].dest = 1;  grafico->bordo[0].peso = -1;  // aggiunge bordo 0-2 (o A-C nella figura sopra) graph->edge[1].src = 0;  grafico->bordo[1].dest = 2;  grafico->bordo[1].peso = 4;  // aggiunge il bordo 1-2 (o B-C nella figura sopra) graph->edge[2].src = 1;  grafico->bordo[2].dest = 2;  grafico->bordo[2].peso = 3;  // aggiunge il bordo 1-3 (o B-D nella figura sopra) graph->edge[3].src = 1;  grafico->bordo[3].dest = 3;  grafico->bordo[3].peso = 2;  // aggiunge il bordo 1-4 (o B-E nella figura sopra) graph->edge[4].src = 1;  grafico->bordo[4].dest = 4;  grafico->bordo[4].peso = 2;  // aggiunge il bordo 3-2 (o D-C nella figura sopra) graph->edge[5].src = 3;  grafico->bordo[5].dest = 2;  grafico->bordo[5].peso = 5;  // aggiunge bordo 3-1 (o D-B nella figura sopra) graph->edge[6].src = 3;  grafico->bordo[6].dest = 1;  grafico->bordo[6].peso = 1;  // aggiunge il bordo 4-3 (o E-D nella figura sopra) graph->edge[7].src = 4;  grafico->bordo[7].dest = 3;  grafico->bordo[7].peso = -3;    // Chiamata di funzione BellmanFord(graph, 0);  restituire 0; }>
Giava 
// 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);>
Produzione 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Analisi della complessità dell'algoritmo di Bellman-Ford :

  • Complessità temporale quando il grafico è connesso:
    • Caso migliore: O(E), quando l'array di distanza dopo il 1° e il 2° rilassamento sono uguali, possiamo semplicemente interrompere l'ulteriore elaborazione
    • Caso medio: O(V*E)
    • Caso peggiore: O(V*E)
  • Complessità temporale quando il grafico è disconnesso :
    • Tutti i casi: O(E*(V^2))
  • Spazio ausiliario: O(V), dove V è il numero di vertici nel grafico.

Applicazioni dell’algoritmo di Bellman Ford:

  • Instradamento di rete: Bellman-Ford viene utilizzato nelle reti di computer per trovare i percorsi più brevi nelle tabelle di instradamento, aiutando i pacchetti di dati a navigare in modo efficiente attraverso le reti.
  • Navigazione GPS: i dispositivi GPS utilizzano Bellman-Ford per calcolare i percorsi più brevi o più veloci tra le località, aiutando le app e i dispositivi di navigazione.
  • Trasporti e logistica: L’algoritmo di Bellman-Ford può essere applicato per determinare i percorsi ottimali per i veicoli nei trasporti e nella logistica, riducendo al minimo il consumo di carburante e il tempo di viaggio.
  • Sviluppo del gioco: Bellman-Ford può essere utilizzato per modellare il movimento e la navigazione all'interno dei mondi virtuali nello sviluppo di giochi, dove percorsi diversi possono avere costi o ostacoli variabili.
  • Robotica e veicoli autonomi: L'algoritmo aiuta nella pianificazione del percorso per robot o veicoli autonomi, considerando gli ostacoli, il terreno e il consumo di energia.

Svantaggio dell’algoritmo di Bellman Ford:

  • L'algoritmo di Bellman-Ford fallirà se il grafico contiene un ciclo di fronti negativi.

Articoli correlati sugli algoritmi del percorso più breve a sorgente singola: