सिंगल-सोर्स शॉर्टेस्ट पाथ, आर्बिट्रेरी वेट (बेलमैन-फोर्ड एल्गोरिदम)

सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम (मनमाने वजन पॉजिटिव या नेगेटिव के लिए) को बेलमैन-फोर्ड एल्गोरिदम के रूप में भी जाना जाता है, जिसका उपयोग सोर्स वर्टेक्स से किसी अन्य वर्टेक्स तक न्यूनतम दूरी खोजने के लिए किया जाता है। इस एल्गोरिदम और डिज्क्स्ट्रा के एल्गोरिदम के बीच मुख्य अंतर यह है कि डिज्क्स्ट्रा के एल्गोरिदम में हम नेगेटिव वेट को संभाल नहीं सकते, लेकिन यहां हम इसे आसानी से संभाल सकते हैं।

बेलमैन-फोर्ड एल्गोरिदम बॉटम-अप तरीके से दूरी ढूंढता है। सबसे पहले यह उन दूरियों को ढूंढता है जिनके पथ में केवल एक एज होता है। उसके बाद सभी संभावित समाधान खोजने के लिए पथ की लंबाई बढ़ाता है।

इनपुट − ग्राफ का कॉस्ट मैट्रिक्स:

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)

इनपुट − डिस्टेंस लिस्ट, प्रेडिसेसर लिस्ट और सोर्स वर्टेक्स।

आउटपुट − ट्रू, जब नेगेटिव साइकिल मिलती है।

Begin
    iCount := 1
    maxEdge := n * (n - 1) / 2 //n वर्टेक्स की संख्या है
    ग्राफ के सभी वर्टेक्स v के लिए, do
        dist[v] := ∞
        pred[v] := φ
    done
    dist[source] := 0
    eCount := ग्राफ में मौजूद एज की संख्या
    edgeList नामक एज लिस्ट बनाएं
    while iCount < n, do
        for i := 0 to eCount, do
            if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] एज i के लिए) then
                dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] एज i के लिए)
                pred[edgeList[i].v] := edgeList[i].u
            done
        done
        iCount := iCount + 1
        ग्राफ में सभी वर्टेक्स i के लिए, do
            if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] एज i के लिए), then
                return true
            done
        return false
End

उदाहरण (C++)

#include 
#include 
#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; //प्रारंभिक वर्टेक्स के लिए दूरी 0 है
    ecount = makeEdgeList(edgeList); //edgeList निर्माण
    while(icount < V){ //इटरेशन की संख्या (वर्टेक्स - 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