बेलमैन फोर्ड एल्गोरिथम गतिशील प्रोग्रामिंग एल्गोरिथम है जिसका उपयोग किसी भी शीर्ष के सबसे छोटे पथ को खोजने के लिए किया जाता है, जिसे शुरुआती शीर्ष के रूप में माना जाता है। यह एल्गोरिथ्म पुनरावृत्त विधि का अनुसरण करता है और लगातार सबसे छोटा पथ खोजने का प्रयास करता है। भारित ग्राफ़ पर बेलमैन फोर्ड एल्गोरिथम।
यह एल्गोरिथम 1955 में अल्फांसो शिम्बेल द्वारा प्रस्तावित किया गया था। एल्गोरिथम में रिचर्ड बेलमैन और लेस्टर फोर्ड द्वारा संशोधन हैं। वर्ष 1956 और 1958 में इसी एल्गोरिथम के कारण इसका नाम बेलमैन फोर्ड एल्गोरिथम रखा गया था . इस एल्गोरिथम को 1957 में ईवर्ड एफ. मूर द्वारा भी संशोधित किया गया था, जिसने इसका नाम बेलमैन-फोर्ड-मूर एल्गोरिथम कर दिया। ।
यह एल्गोरिदम बेहतर है क्योंकि यह किनारे के नकारात्मक भार के साथ संभाल सकता है। हालांकि एल्गोरिथम डिजस्ट्रा के एल्गोरिथम की तुलना में धीमा है, यह एक बेहतर है क्योंकि यह अधिक बहुमुखी प्रकार के ग्राफ़ को संभालता है।
एल्गोरिदम
Input : weighted graph and starting vertex Output : shortest distance between all vertices from the src. For negative weight cycle, the same will be returned as the weight cannot be calculated.
एल्गोरिदम
Step 1 : This is the initialisation step, an array is created that stores the distance of all vertices from the initial vertex. The array say dist[] of size equal to the number of vertices in the graph. Step 2 : Calculate the shortest distance of vertex. Loop through step 3 for n-1 number of times ( n is the number of vertices of graph). Step 3 : Follow following steps for each edge i-j Step 3.1 : If dist[v] > dist[u] + weight[uv]. Then, dist[v] = dist[u] + weight[uv]. Step 4 : Check and flag if there is any negative cycle. If step 3.1 executes then there is a negative cycle.
नकारात्मक चक्र :यदि नियमित किनारे ट्रैवर्सल से छोटा पथ मौजूद है, तो एक नकारात्मक चक्र होता है।
उदाहरण
आइए कुछ ग्राफ़ संबंधी समस्याओं को हल करके एल्गोरिथम के बारे में अधिक जानें।
आप ग्राफ़ के सभी शीर्षों और किनारों को उनके साथ जुड़े वज़न के साथ देख सकते हैं।
आइए वर्टेक्स ए और वर्टेक्स ई . के बीच सबसे कम दूरी का पता लगाएं बेलमैन-फोर्ड एल्गोरिथम का उपयोग करना।
स्रोत शीर्ष (ए) को शून्य 0 पर सेट करें और बाकी दूरियों को अनंत ∞ पर सेट करें।
A B C D E 0 ∞ ∞ ∞ ∞
किनारे का वजन जांचा जा रहा है A-B और फिर ए-सी ,
A-B के लिए हमारे पास केवल एक पथ है लेकिन A-C के लिए, हमारे पास दो पथ हैं जिन्हें पार किया जा सकता है और हम जाँच करेंगे कि कौन सा सबसे छोटा है।
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ - for (A-B) 0 -2 3 ∞ ∞ - for (A-C)
अगले शीर्ष के लिए, हम प्रारंभिक शीर्ष के लिए और सबसे छोटी दूरी की गणना करेंगे।
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ 0 -2 3 3 10
इसलिए एल्गोरिथम का उपयोग करते हुए सबसे कम दूरी 10 है। पथ को पार करना A-B-E . इसके प्रयोग से हमने यह भी पाया कि एक नकारात्मक चक्र है।
उदाहरण
#include <bits/stdc++.h>
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void BellmanFord(struct Graph* graph, int src) {
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; 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_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return;
}
}
printf("Vertex :\t\t\t ");
for (int i = 0; i < V; ++i)
printf("%d \t", i);
printf("\nDistance From Source : ");
for (int i = 0; i < V; ++i)
printf("%d \t",dist[i]);
return;
}
int main() {
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
} आउटपुट
Vertex : 0 1 2 3 4 Distance From Source : 0 -1 2 -2 1