সিঙ্গেল-সোর্স শর্টেস্ট পাথস, আর্বিট্রারি ওয়েটস (বেলমান-ফোর্ড)

সিঙ্গেল সোর্স শর্টেস্ট পাথ অ্যালগরিদম (আربیট্রারি ওয়েট পজিটিভ বা 네가েটিভ) কে বেলমান-ফোর্ড অ্যালগরিদম বলা হয়, যা সোর্স ভার্টেক্স থেকে অন্য যেকোনো ভার্টেক্স পর্যন্ত মিনিমাম ডিস্ট্যান্স বের করতে ব্যবহৃত হয়। এই অ্যালগরিদমের ডিকস্ট্রার অ্যালগরিদমের সাথে মূল পার্থক্য হলো, ডিকস্ট্রাতে 네가েটিভ ওয়েট হ্যান্ডেল করা যায় না, কিন্তু এখানে সহজেই হ্যান্ডেল করা যায়।

বেলমান-ফোর্ড অ্যালগরিদম বটম-আপ ম্যানারে ডিস্ট্যান্স বের করে। প্রথমে সেটা সেই ডিস্ট্যান্স বের করে যেগুলোর পাথে শুধু একটা এজ থাকে। তারপর পাথ লেন্থ বাড়িয়ে সব সম্ভাব্য সমাধান বের করে।

ইনপুট − গ্রাফের কস্ট ম্যাট্রিক্স:

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, যখন একটি 네가েটিভ সাইকেল পাওয়া যায়।

Begin
    iCount := 1
    maxEdge := n * (n - 1) / 2 //n is number of vertices
    for all vertices v of the graph, do
        dist[v] := ∞
        pred[v] := φ
    done
    dist[source] := 0
    eCount := number of edges present in the graph
    create edge list named edgeList
    while iCount < n, do
        for i := 0 to eCount, do
            if 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
            done
        done
        iCount := iCount + 1
        for all vertices i in the graph, do
            if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i), then
                return true
            done
        return false
End

উদাহরণ (C++)

#include 
#include 
#define V 5
#define INF 999
using namespace std;
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);
    while(icount < V){
        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