logo

TechCodeview

Algoritme Bellman-Ford

Imagineu que teniu un mapa amb diferents ciutats connectades per carreteres, cada carretera amb una distància determinada. El Algorisme de Bellman-Ford és com una guia que us ajuda a trobar el camí més curt d'una ciutat a totes les altres ciutats, encara que algunes carreteres tinguin longituds negatives. És com una GPS per a ordinadors, útil per esbrinar la manera més ràpida d'arribar d'un punt a un altre en una xarxa. En aquest article, veurem més de prop com funciona aquest algorisme i per què és tan útil per resoldre problemes quotidians.

Algoritme Bellman-Ford

Taula de contingut



Algoritme Bellman-Ford

Bellman-Ford és un font única algorisme del camí més curt que determina el camí més curt entre un vèrtex font donat i tots els altres vèrtexs d'un gràfic. Aquest algorisme es pot utilitzar en tots dos ponderat i sense ponderar gràfics.

prime no code in java

A Bellman-Ford L'algorisme també està garantit per trobar el camí més curt en un gràfic, de manera similar a algorisme de Dijkstra . Encara que Bellman-Ford és més lent que algorisme de Dijkstra , és capaç de manejar gràfics amb pesos de vora negatiu , cosa que el fa més versàtil. No es pot trobar el camí més curt si existeix a cicle negatiu al gràfic. Si continuem donant la volta al cicle negatiu un nombre infinit de vegades, aleshores el cost del camí continuarà disminuint (tot i que la longitud del camí augmenta). Com a resultat, Bellman-Ford també és capaç de detectar cicles negatius , que és una característica important.

La idea darrere de l'algoritme de Bellman Ford:

El principi principal de l'algorisme de Bellman-Ford és que comença amb una única font i calcula la distància a cada node. La distància es desconeix inicialment i se suposa que és infinita, però a mesura que passa el temps, l'algoritme relaxa aquests camins identificant uns quants camins més curts. Per tant, es diu que es basa en Bellman-Ford Principi de relaxació .

Principi de relaxació de les vores per a Bellman-Ford:

  • Afirma que per al gràfic que té N vèrtexs, totes les arestes han d'estar relaxades N-1 vegades per calcular el camí més curt de la font única.
  • Per detectar si existeix un cicle negatiu o no, relaxeu tota la vora una vegada més i si la distància més curta per a qualsevol node es redueix, podem dir que existeix un cicle negatiu. En resum si relaxem les vores N vegades, i hi ha algun canvi en la distància més curta de qualsevol node entre el N-1r i Nè relaxació que un cicle negatiu existeix, en cas contrari no existeix.

Per què Relaxing Edges N-1 vegades, ens ofereix el camí més curt d'una sola font?

En el pitjor dels casos, un camí més curt entre dos vèrtexs pot tenir com a màxim N-1 vores, on N és el nombre de vèrtexs. Això es deu a un camí senzill en un gràfic amb N els vèrtexs poden tenir com a màxim N-1 vores, ja que és impossible formar un bucle tancat sense revisar un vèrtex.

Per relaxar les vores N-1 vegades, l'algoritme de Bellman-Ford assegura que les estimacions de distància per a tots els vèrtexs s'han actualitzat als seus valors òptims, suposant que el gràfic no conté cicles de pes negatiu accessibles des del vèrtex font. Si un gràfic conté un cicle de pes negatiu accessible des del vèrtex font, l'algoritme pot detectar-lo després N-1 iteracions, ja que el cicle negatiu altera les longituds de camí més curtes.

En resum, vores relaxants N-1 vegades a l'algorisme de Bellman-Ford garanteix que l'algoritme ha explorat tots els camins possibles de longitud fins a N-1 , que és la longitud màxima possible d'un camí més curt en un gràfic amb N vèrtexs. Això permet que l'algoritme calculi correctament els camins més curts des del vèrtex font fins a tots els altres vèrtexs, atès que no hi ha cicles de pes negatiu.

mergesort java

Per què la reducció de la distància en la relaxació N indica l'existència d'un cicle negatiu?

Com s'ha comentat anteriorment, cal aconseguir els camins més curts d'una sola font cap a tots els altres nodes N-1 relaxacions. Si la relaxació N'è redueix encara més la distància més curta per a qualsevol node, implica que s'ha travessat una vegada més una vora amb pes negatiu. És important tenir en compte que durant el N-1 relaxacions, vam suposar que cada vèrtex només es recorre una vegada. Tanmateix, la reducció de la distància durant la relaxació N'th indica tornar a visitar un vèrtex.

Funcionament de l'algoritme Bellman-Ford per detectar el cicle negatiu al gràfic:

Suposem que tenim un gràfic que es mostra a continuació i volem trobar si existeix un cicle negatiu o no utilitzant Bellman-Ford.

Gràfic inicial

Pas 1: Inicialitzar una matriu de distàncies Dist[] per emmagatzemar la distància més curta per a cada vèrtex des del vèrtex font. Inicialment la distància de la font serà 0 i la distància d'altres vèrtexs serà INFINITY.

Inicialitzar una matriu de distància

Pas 2: Comença a relaxar les vores, durant la 1a Relaxació:

  • Distància actual de B> (Distància de A) + (Pes de A a B), és a dir, infinit> 0 + 5
    • Per tant, Dist[B] = 5

1r Relaxació

Pas 3: Durant la 2a relaxació:
  • Distància actual de D> (Distància de B) + (Pes de B a D), és a dir, infinit> 5 + 2
    • Dist[D] = 7
  • Distància actual de C> (Distància de B) + (Pes de B a C), és a dir, infinit> 5 + 1
    • Dist[C] = 6

2n Relaxació

Pas 4: Durant la 3a relaxació:

màquina virtual java
  • Distància actual de F> (Distància de D) + (Pes de D a F), és a dir, infinit> 7 + 2
    • Dist[F] = 9
  • Distància actual de E> (Distància de C ) + (Pes de C a E), és a dir, infinit> 6 + 1
    • Dist[E] = 7

3r Relaxació

Pas 5: Durant la 4a relaxació:

  • Distància actual de D> (Distància de E) + (Pes de E a D), és a dir, 7> 7 + (-1)
    • Dist[D] = 6
  • Distància actual de E> (Distància de F ) + (Pes de F a E), és a dir, 7> 9 + (-3)
    • Dist[E] = 6

4t Relaxació

Pas 6: Durant la 5a relaxació:

  • Distància actual de F> (Distància de D) + (Pes de D a F), és a dir, 9> 6 + 2
    • Dist[F] = 8
  • Distància actual de D> (Distància de E ) + (Pes de E a D), és a dir, 6> 6 + (-1)
    • Dist[D] = 5
  • Com que el gràfic h 6 vèrtexs, per tant, durant la 5a relaxació s'hauria d'haver calculat la distància més curta per a tots els vèrtexs.

5è Relaxació

Pas 7: Ara la relaxació final, és a dir, la 6a relaxació, hauria d'indicar la presència de cicle negatiu si hi ha algun canvi en la matriu de distància de la 5a relaxació.

Durant la 6a relaxació, es poden observar els següents canvis:

  • Distància actual de E> (Distància de F) + (Pes de F a E), és a dir, 6> 8 + (-3)
    • Dist[E]=5
  • Distància actual de F> (Distància de D) + (Pes de D a F), és a dir, 8> 5 + 2
    • Dist[F]=7

Atès que observem canvis en la matriu de distància. Per tant, podem concloure la presència d'un cicle negatiu al gràfic.

6è Relaxació

bucle infinit

Resultat: Hi ha un cicle negatiu (D->F->E) al gràfic.

Algorisme per trobar el cicle negatiu en un gràfic ponderat dirigit utilitzant Bellman-Ford:

  • Inicialitzar la matriu de distància dist[] per a cada vèrtex ' en 'com dist[v] = INFINIT .
  • Assumiu qualsevol vèrtex (diguem '0') com a font i assigneu-lo dist = 0 .
  • Relaxa't tot arestes (u,v,pes) N-1 vegades segons la condició següent:
    • dist[v] = mínim (dist[v], distància[u] + pes)
  • Ara, relaxeu totes les vores una vegada més, és a dir Nè temps i a partir dels dos casos següents podem detectar el cicle negatiu:
    • Cas 1 (existeix cicle negatiu): per a qualsevol aresta (u, v, pes), si dist[u] + pes
    • Cas 2 (sense cicle negatiu): el cas 1 falla per a totes les vores.

Maneig de gràfics desconnectats a l'algoritme:

L'algorisme i el programa anteriors poden no funcionar si el gràfic donat està desconnectat. Funciona quan tots els vèrtexs són accessibles des del vèrtex font 0 .
Per gestionar gràfics desconnectats, podem repetir l'algorisme anterior per als vèrtexs que tenen distància = INFINIT, o simplement pels vèrtexs que no es visiten.

A continuació es mostra la implementació de l'enfocament anterior:

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->Nombre de vèrtexs, E-> Nombre d'arestes int V, E;  // El gràfic es representa com una matriu d'arestes.  struct Edge* vora; }; // Crea un gràfic amb V vèrtexs i E arestes struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph;  gràfic->V = V;  gràfic->E = E;  gràfic-> vora = nova vora[E];  gràfic de retorn; } // Una funció d'utilitat utilitzada per imprimir la solució void printArr(int dist[], int n) { printf('Vertex Distance from Source
');  per (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 = gràfic->E;  int dist[V];  // Pas 1: inicialitzeu les distàncies des de src a tots els altres // vèrtexs com a INFINIT per a (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->vora[j].src;  int v = graph->edge[j].dest;  int pes = gràfic->aresta[j].pes;  si (dist[u] != INT_MAX && dist[u] + pes< 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->vora[i].src;  int v = graph->edge[i].dest;  int pes = gràfic->aresta[i].pes;  si (dist[u] != INT_MAX && dist[u] + pes< 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->vora[0].src = 0;  gràfic-> vora[0].dest = 1;  gràfic->aresta[0].pes = -1;  // afegeix vora 0-2 (o A-C a la figura anterior) graph->edge[1].src = 0;  gràfic->aresta[1].dest = 2;  gràfic->aresta[1].pes = 4;  // afegeix l'aresta 1-2 (o B-C a la figura anterior) graph->edge[2].src = 1;  gràfic->aresta[2].dest = 2;  gràfic->aresta[2].pes = 3;  // afegeix l'aresta 1-3 (o B-D a la figura anterior) graph->edge[3].src = 1;  gràfic-> vora[3].dest = 3;  gràfic->aresta[3].pes = 2;  // afegeix l'aresta 1-4 (o B-E a la figura anterior) graph->edge[4].src = 1;  gràfic-> vora[4].dest = 4;  gràfic->aresta[4].pes = 2;  // afegeix l'aresta 3-2 (o D-C a la figura anterior) graph->edge[5].src = 3;  gràfic->aresta[5].dest = 2;  gràfic->aresta[5].pes = 5;  // afegeix l'aresta 3-1 (o D-B a la figura anterior) graph->edge[6].src = 3;  gràfic->aresta[6].dest = 1;  gràfic->aresta[6].pes = 1;  // afegeix l'aresta 4-3 (o E-D a la figura anterior) graph->edge[7].src = 4;  gràfic-> vora[7].dest = 3;  gràfic->aresta[7].pes = -3;    // Crida a la funció BellmanFord(graph, 0);  retorn 0; }>>>Java
Python 3 
# 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);>
Sortida 
Vertex Distance from Source 0 0 1 -1 2 2 3 -2 4 1>

Anàlisi de complexitat de l'algoritme Bellman-Ford :

  • Complexitat temporal quan el gràfic està connectat:
    • Millor cas: O(E), quan la matriu de distància després de la 1a i la 2a relaxació són iguals, simplement podem aturar el processament posterior
    • Cas mitjà: O(V*E)
    • Pitjor dels casos: O(V*E)
  • Complexitat temporal quan el gràfic està desconnectat :
    • Tots els casos: O(E*(V^2))
  • Espai auxiliar: O(V), on V és el nombre de vèrtexs del gràfic.

Aplicacions de l'algoritme de Bellman Ford:

  • Enrutament de xarxa: Bellman-Ford s'utilitza en xarxes d'ordinadors per trobar els camins més curts a les taules d'encaminament, ajudant els paquets de dades a navegar de manera eficient per les xarxes.
  • Navegació GPS: els dispositius GPS utilitzen Bellman-Ford per calcular les rutes més curtes o ràpides entre ubicacions, ajudant a les aplicacions i dispositius de navegació.
  • Transport i logística: L'algoritme de Bellman-Ford es pot aplicar per determinar els camins òptims per als vehicles en transport i logística, minimitzant el consum de combustible i el temps de viatge.
  • Desenvolupament del joc: Bellman-Ford es pot utilitzar per modelar el moviment i la navegació dins dels mons virtuals en el desenvolupament de jocs, on diferents camins poden tenir costos o obstacles diferents.
  • Robòtica i vehicles autònoms: L'algoritme ajuda a planificar la ruta de robots o vehicles autònoms, tenint en compte els obstacles, el terreny i el consum d'energia.

Inconvenient de l'algoritme de Bellman Ford:

  • L'algorisme de Bellman-Ford fallarà si el gràfic conté algun cicle de vora negatiu.

Articles relacionats sobre algorismes de camí més curt d'una sola font: