বেলম্যান-ফোর্ড অ্যালগরিদম ব্যবহার করা হয় সোর্স ভার্টেক্স থেকে অন্য যেকোনো ভার্টেক্স পর্যন্ত ন্যূনতম দূরত্ব খুঁজে বের করতে। এই অ্যালগরিদমের মূল পার্থক্য ডিজ্কস্ট্রার অ্যালগরিদমের সাথে হচ্ছে, ডিজ্কস্ট্রায় আমরা নেগেটিভ ওজন হ্যান্ডেল করতে পারি না, কিন্তু এখানে সেটি সহজে হ্যান্ডেল করা যায়।
বেলম্যান-ফোর্ড অ্যালগরিদম বটম-আপ পদ্ধতিতে দূরত্ব খুঁজে বের করে। প্রথমে সে সেই দূরত্বগুলো খুঁজে বের করে যেগুলোর পথে শুধু একটি এজ থাকে। তারপর পথের দৈর্ঘ্য বাড়িয়ে সব সম্ভাব্য সমাধান খুঁজে বের করে।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের কস্ট ম্যাট্রিক্স: 0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0 আউটপুট: সোর্স ভার্টেক্স: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 গ্রাফে কোনো নেগেটিভ এজ সাইকেল নেই
এলগরিদম
bellmanFord(dist, pred, source)
ইনপুট: দূরত্ব লিস্ট, প্রিডিসেসর লিস্ট, এবং সোর্স ভার্টেক্স।
আউটপুট: নেগেটিভ সাইকেল পাওয়া গেলে true।
শুরু
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] + (cost[u,v] for edge i)
dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i)
pred[edgeList[i].v] := edgeList[i].u
শেষ লুপ
iCount := iCount + 1
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
যদি dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i),
তবে return true
শেষ লুপ
return false
শেষ
উদাহরণ (C++ কোড)
#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 < V; i++) {
for(j = 0; j < V; j++) {
if(costMat[i][j] != costMat[j][i]) {
return 1; // গ্রাফ ডায়রেক্টেড
}
}
}
return 0; // গ্রাফ অননির্দেশিত
}
int makeEdgeList(edge *eList) {
// গ্রাফের এজ থেকে এজলিস্ট তৈরি করুন
int count = -1;
if(isDiagraph()) {
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
if(costMat[i][j] != 0 && costMat[i][j] != INF) {
count++; // ডায়রেক্টেড গ্রাফ হলে এজ পাওয়া যায়
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
} else {
for(int i = 0; i < V; i++) {
for(int j = 0; j < i; j++) {
if(costMat[i][j] != INF) {
count++; // অননির্দেশিত গ্রাফ হলে এজ পাওয়া যায়
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
}
return count+1;
}
int bellmanFord(int *dist, int *pred, int src) {
int icount = 1, ecount, max = V*(V-1)/2;
edge edgeList[max];
for(int i = 0; i < V; i++) {
dist[i] = INF; // অনন্ত দিয়ে ইনিশিয়ালাইজ
pred[i] = -1; // কোনো প্রিডিসেসর পাওয়া যায়নি
}
dist[src] = 0; // শুরুর ভার্টেক্সের দূরত্ব ০
ecount = makeEdgeList(edgeList); // edgeList গঠন
while(icount < V) {
// ইটারেশনের সংখ্যা (Vertex - 1)
for(int i = 0; i < ecount; i++) {
if(dist[edgeList[i].v] > 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 < ecount; i++) {
if(dist[edgeList[i].v] > 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 < V; i++)
cout << setw(3) << i << " ";
cout << endl;
cout << "Dist: ";
for(int i = 0; i < V; i++)
cout << setw(3) << dist[i] << " ";
cout << endl;
cout << "Pred: ";
for(int i = 0; i < V; i++)
cout << setw(3) << pred[i] << " ";
cout << endl;
}
int main() {
int dist[V], pred[V], source, report;
source = 2;
report = bellmanFord(dist, pred, source);
cout << "Source Vertex: " << source << endl;
display(dist, pred);
if(report)
cout << "The graph has a negative edge cycle" << endl;
else
cout << "The graph has no negative edge cycle" << endl;
}
আউটপুট
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
