Algorithme de Bellman Ford

L'algorithme de Bellman Ford nous aide à trouver le chemin le plus court entre un sommet et tous les autres sommets d'un graphe pondéré.

Il est similaire à l'algorithme de Dijkstra mais il peut fonctionner avec des graphes dans lesquels les arêtes peuvent avoir des poids négatifs.

Pourquoi aurait-on jamais des bords avec des poids négatifs dans la vraie vie?

Les bords de poids négatifs peuvent sembler inutiles au début, mais ils peuvent expliquer de nombreux phénomènes comme les flux de trésorerie, la chaleur libérée / absorbée lors d'une réaction chimique, etc.

Par exemple, s'il existe différentes façons d'atteindre un produit chimique A à un autre produit chimique B, chaque méthode aura des sous-réactions impliquant à la fois la dissipation et l'absorption de chaleur.

Si nous voulons trouver l'ensemble des réactions où une énergie minimale est requise, nous devrons être en mesure de prendre en compte l'absorption de chaleur sous forme de poids négatifs et la dissipation de chaleur comme poids positifs.

Pourquoi devons-nous faire attention aux pondérations négatives?

Les bords de poids négatifs peuvent créer des cycles de poids négatifs, c'est-à-dire un cycle qui réduira la distance totale du trajet en revenant au même point.

Les cycles de poids négatifs peuvent donner un résultat incorrect en essayant de trouver le chemin le plus court

Les algorithmes de chemin le plus court comme l'algorithme de Dijkstra qui ne sont pas capables de détecter un tel cycle peuvent donner un résultat incorrect car ils peuvent passer par un cycle de poids négatif et réduire la longueur du chemin.

Comment fonctionne l'algorithme de Bellman Ford

L'algorithme de Bellman Ford fonctionne en surestimant la longueur du chemin entre le sommet de départ et tous les autres sommets. Ensuite, il assouplit de façon itérative ces estimations en trouvant de nouveaux chemins plus courts que les chemins précédemment surestimés.

En faisant cela à plusieurs reprises pour tous les sommets, nous pouvons garantir que le résultat est optimisé.

Étape-1 pour l'algorithme de Bellman Ford Étape-2 pour l'algorithme de Bellman Ford Étape-3 pour l'algorithme de Bellman Ford Étape-4 pour l'algorithme de Bellman Ford Étape-5 pour l'algorithme de Bellman Ford Étape-6 pour l'algorithme de Bellman Ford

Pseudocode Bellman Ford

Nous devons maintenir la distance de chemin de chaque sommet. Nous pouvons stocker cela dans un tableau de taille v, où v est le nombre de sommets.

Nous voulons également pouvoir obtenir le chemin le plus court, pas seulement connaître la longueur du chemin le plus court. Pour cela, nous mappons chaque sommet au sommet qui a mis à jour sa longueur de chemin pour la dernière fois.

Une fois l'algorithme terminé, nous pouvons revenir du sommet de destination au sommet source pour trouver le chemin.

 fonction bellmanFord (G, S) pour chaque sommet V dans G distance (V) <- infini précédent (V) <- distance NULL (S) <- 0 pour chaque sommet V dans G pour chaque arête (U, V) dans G tempDistance <- distance (U) + edge_weight (U, V) if tempDistance <distance (V) distance (V) <- tempDistance previous (V) <- U pour chaque bord (U, V) in G Si distance (U) + edge_weight (U, V) <distance (V) Error: Negative Cycle Exists return distance (), previous ()

Bellman Ford contre Dijkstra

L'algorithme de Bellman Ford et l'algorithme de Dijkstra ont une structure très similaire. Alors que Dijkstra ne regarde que les voisins immédiats d'un sommet, Bellman passe par chaque arête à chaque itération.

Algorithme de Dijkstra vs Bellman Ford

Exemples Python, Java et C / C ++

Python Java C C ++ 
 # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)
 // Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )
 // Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )
 // Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )

Complexité de Bellman Ford

Complexité temporelle

Meilleure complexité de cas O (E)
Complexité moyenne des cas O (VE)
Pire complexité des cas O (VE)

Complexité spatiale

Et, la complexité de l'espace est O(V).

Applications d'algorithme de Bellman Ford

  1. Pour calculer les chemins les plus courts dans les algorithmes de routage
  2. Pour trouver le chemin le plus court

Articles intéressants...