बेलमैन-फोर्ड एल्गोरिदम का उपयोग स्रोत शीर्ष से किसी अन्य शीर्ष तक की न्यूनतम दूरी खोजने के लिए किया जाता है। इस एल्गोरिदम और डिज्क्स्ट्रा के एल्गोरिदम के बीच मुख्य अंतर यह है कि डिज्क्स्ट्रा के एल्गोरिदम में हम नकारात्मक भार को संभाल नहीं सकते, लेकिन यहां हम इसे आसानी से संभाल सकते हैं।
बेलमैन-फोर्ड एल्गोरिदम बॉटम-अप तरीके से दूरी ढूंढता है। सबसे पहले, यह उन दूरियों को ढूंढता है जिनके पथ में केवल एक किनारा होता है। उसके बाद पथ की लंबाई बढ़ाकर सभी संभावित समाधान ढूंढता है।
इनपुट और आउटपुट
इनपुट: ग्राफ का लागत मैट्रिक्स: 0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0 आउटपुट: स्रोत शीर्ष: 2 शीर्ष: 0 1 2 3 4 दूरी: -4 -2 0 3 -6 पूर्ववर्ती: 4 2 -1 0 1 ग्राफ में कोई नकारात्मक एज चक्र नहीं है
एल्गोरिदम
bellmanFord(dist, pred, source)
इनपुट: दूरी सूची, पूर्ववर्ती सूची, और स्रोत शीर्ष।
आउटपुट: जब नकारात्मक चक्र मिला तो सच।
शुरू iCount := 1 maxEdge := n * (n - 1) / 2 //n शीर्षों की संख्या है ग्राफ के सभी शीर्ष v के लिए, करें dist[v] := ∞ pred[v] := φ किया dist[source] := 0 eCount := ग्राफ में मौजूद किनारों की संख्या edgeList नामक एज सूची बनाएं जब तक iCount < n, करें i := 0 से eCount तक, करें यदि dist[edgeList[i].v] > dist[edgeList[i].u] + (किनारे i के लिए cost[u,v]) dist[edgeList[i].v] > dist[edgeList[i].u] + (किनारे i के लिए cost[u,v]) pred[edgeList[i].v] := edgeList[i].u किया किया iCount := iCount + 1 ग्राफ में सभी शीर्ष i के लिए, करें यदि dist[edgeList[i].v] > dist[edgeList[i].u] + (किनारे i के लिए cost[u,v]), तो वापस करें सच किया वापस करें गलत अंत
उदाहरण
#include<iostream> #include<iomanip> #define V 5 #define INF 999 using namespace std; //ग्राफ का लागत मैट्रिक्स (निर्देशित) शीर्ष 5 int costMat[V][V] = { {0, 6, INF, 7, INF}, {INF, 0, 5, 8, -4}, {INF, -2, 0, INF, INF}, {INF, INF, -3, 0, 9}, {2, INF, 7, INF, 0} }; typedef struct { int u, v, cost; }edge; int isDiagraph() { //जांचें कि ग्राफ निर्देशित है या नहीं int i, j; for(i = 0; i dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) { //किनारे को रिलैक्स करें और पूर्ववर्ती सेट करें dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]; pred[edgeList[i].v] = edgeList[i].u; } } icount++; } //नकारात्मक चक्र के लिए परीक्षण for(int i = 0; i dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) { return 1; //इंगित करता है कि ग्राफ में नकारात्मक चक्र है } } return 0; //कोई नकारात्मक चक्र नहीं } void display(int *dist, int *pred) { cout << "Vert: "; for(int i = 0; i
आउटपुट
Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle
