C++ তে বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm)

বেলম্যান-ফোর্ড অ্যালগরিদম একটি ডাইনামিক প্রোগ্রামিং অ্যালগরিদম যা ওজনযুক্ত গ্রাফে (weighted graph) একক সোর্স থেকে সব নোড পর্যন্ত ন্যূনতম পথ খুঁজে বের করে। নেগেটিভ ওজন वाले এজ হ্যান্ডেল করতে পারে, যা ডিক্সট্রা অ্যালগরিদমে সম্ভব নয়।

ইতিহাস

১৯৫৫: অ্যাফনসো শিমবেল প্রস্তাব করেন।
১৯৫৬, ১৯৫৮: রিচার্ড বেলম্যান ও לס্টার ফোর্ড সংশোধন করেন → নামकरण Bellman-Ford।
১৯৫৭: এডওয়ার্ড এফ. মুর সংশোধন করেন → Bellman-Ford-Moore।

অ্যালগরিদম

ইনিশিয়ালাইজেশন: dist[] অ্যারে তৈরি করুন, সোর্স=০, বাকি=∞।
রিল্যাক্সেশন: V-1 বার সব এজ traverser করুন। যদি dist[v] > dist[u] + weight(u,v) হয়, তবে আপডেট করুন।
নেগেটিভ সাইকেল চেক: একবার আর রিল্যাক্স করুন। আপডেট হলে নেগেটিভ সাইকেল আছে।

উদাহরণ (গ্রাফ ছবি সহ)

সোর্স A(0) থেকে E(4) পর্যন্ত ন্যূনতম দূরত্ব = ১০ (পথ: A-B-E)। নেগেটিভ সাইকেল পাওয়া যায়।

C++ কোড উদাহরণ

#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, 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 w = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src, v = graph->edge[i].dest, w = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            printf("Graph contains negative weight cycle");
            return;
        }
    }
    printf("Vertex: "); 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]);
}

int main() {
    int V = 5, E = 8;
    struct Graph* graph = createGraph(V, E);
    // এজ যোগ করুন...
    BellmanFord(graph, 0);
    return 0;
}

আউটপুট

Vertex : 0 1 2 3 4
Distance From Source : 0 -1 2 -2 1