बेलमैन-फोर्ड एल्गोरिदम एक डायनामिक प्रोग्रामिंग एल्गोरिदम है जिसका उपयोग किसी भी शीर्ष के सबसे छोटे पथ को खोजने के लिए किया जाता है जिसे एक शीर्ष से प्रारंभिक शीर्ष के रूप में माना जाता है। यह एल्गोरिदम पुनरावृत्त विधि का पालन करता है और लगातार सबसे छोटा पथ खोजने का प्रयास करता है। बेलमैन-फोर्ड एल्गोरिदम भारित ग्राफ पर काम करता है।
यह एल्गोरिदम 1955 में अल्फोंसो शिमबेल द्वारा प्रस्तावित किया गया था। एल्गोरिदम में 1956 और 1958 में रिचर्ड बेलमैन और लेस्टर फोर्ड द्वारा संशोधन किए गए, जिसके कारण इस एल्गोरिदम का नाम बेलमैन-फोर्ड एल्गोरिदम रखा गया। इस एल्गोरिदम को 1957 में एडवर्ड एफ. मूर द्वारा भी संशोधित किया गया, जिसने इसका नाम बेलमैन-फोर्ड-मूर एल्गोरिदम बना दिया।
यह एल्गोरिदम बेहतर है क्योंकि यह ऋणात्मक भार वाले किनारों को संभाल सकता है। हालांकि एल्गोरिदम डिज्क्स्ट्रा के एल्गोरिदम से धीमा है, यह एक बेहतर है क्योंकि यह अधिक बहुमुखी प्रकार के ग्राफ को संभालता है।
एल्गोरिदम
इनपुट: भारित ग्राफ और प्रारंभिक शीर्ष आउटपुट: src से सभी शीर्षों के बीच की सबसे छोटी दूरी। ऋणात्मक भार चक्र के लिए, वही वापस किया जाएगा क्योंकि भार की गणना नहीं की जा सकती।
एल्गोरिदम चरण
चरण 1: यह आरंभीकरण चरण है, एक एरे बनाया जाता है जो सभी शीर्षों की प्रारंभिक शीर्ष से दूरी संग्रहीत करता है। एरे कहें dist[] ग्राफ में शीर्षों की संख्या के बराबर आकार का। चरण 2: शीर्ष की सबसे छोटी दूरी की गणना करें। चरण 3 के लिए n-1 बार लूप करें (n ग्राफ के शीर्षों की संख्या है)। चरण 3: प्रत्येक किनारे i-j के लिए निम्नलिखित चरणों का पालन करें चरण 3.1: यदि dist[v] > dist[u] + weight[uv]। तो, dist[v] = dist[u] + weight[uv]। चरण 4: जांचें और फ्लैग करें कि क्या कोई ऋणात्मक चक्र है। यदि चरण 3.1 निष्पादित होता है तो ऋणात्मक चक्र है।
ऋणात्मक चक्र: यदि नियमित किनारे के पारगमन से छोटा पथ मौजूद है, तो ऋणात्मक चक्र है।
उदाहरण
आइए ग्राफ संबंधी कुछ समस्याओं को हल करके एल्गोरिदम के बारे में और जानें।
आप ग्राफ के सभी शीर्षों और किनारों को उनके साथ जुड़े भारों के साथ देख सकते हैं।
आइए शीर्ष A और शीर्ष E के बीच की सबसे छोटी दूरी बेलमैन-फोर्ड एल्गोरिदम का उपयोग करके खोजें।
स्रोत शीर्ष (A) को शून्य 0 पर सेट करें और बाकी दूरियों को अनंत ∞ पर सेट करें।
A B C D E 0 ∞ ∞ ∞ ∞
A-B और फिर A-C के किनारे के भार की जांच करते हुए,
A-B के लिए हमारे पास केवल एक पथ है लेकिन A-C के लिए, हमारे पास दो पथ हैं जिन्हें पार किया जा सकता है और हम जांचेंगे कि कौन सा सबसे छोटा है।
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ - (A-B) के लिए 0 -2 3 ∞ ∞ - (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
