C++ প্রোগ্রাম: DAG-এ SSSP (Single Source Shortest Path) ডিজিক্সট্রা অ্যালগরিদম দিয়ে

এটি একটি C++ প্রোগ্রাম যা DAG (Directed Acyclic Graphs)-এ SSSP (Single Source Shortest Path) বের করতে ডিজিক্সট্রা অ্যালগরিদম ব্যবহার করে। এটি গ্রাফের প্রথম নোড থেকে অন্যান্য সব নোডে সর্বনিম্ন পথের দৈর্ঘ্য দেখায়।

অ্যালগরিদম

Begin
    গ্রাফের এলিমেন্ট ইনপুট নিন।
    function shortestpath():
    ভেরিয়েবল ইনিশিয়ালাইজ করুন
    a[i] = 1, d[i] = 0, s[i].from = 0
    লুপ i = 0 to 3: যদি b[0][i] == 0 তবে continue, অন্যথায় d[i] = b[0][i], s[i].from = 0
    while (c < 4):
        min = INFINITY
        for i = 0 to 3: যদি min <= d[i] বা d[i]==0 বা a[i]==1 তবে continue, অন্যথায় min = d[i]
        for k = 0 to 3: যদি min == d[k] তবে t = k, break
        a[t] = 1
        for j = 0 to 3: যদি a[j]==1 বা b[t][j]==0 তবে continue, অন্যথায় যদি d[j] > d[t]+b[t][j] তবে d[j] আপডেট, s[i].from = t
        c++
    for i = 0 to 3: নোড ১ থেকে নোড ২-এ মিনিমাম কস্ট প্রিন্ট করুন
End

উদাহরণ

#include <iostream>
using namespace std;
#define INFINITY 9999

struct node {
    int from;
} s[4];

int c = 0;

void djikstras(int *a, int b[][4], int *d) {
    int i = 0, j, min, t;
    a[i] = 1;
    d[i] = 0;
    s[i].from = 0;
    for (i = 0; i < 4; i++) {
        if (b[0][i] == 0) continue;
        else {
            d[i] = b[0][i];
            s[i].from = 0;
        }
    }
    while (c < 4) {
        min = INFINITY;
        for (i = 0; i < 4; i++) {
            if (min <= d[i] || d[i] == 0 || a[i] == 1) continue;
            else if (min > d[i]) min = d[i];
        }
        for (int k = 0; k < 4; k++) {
            if (min == d[k]) { t = k; break; }
            else continue;
        }
        a[t] = 1;
        for (j = 0; j < 4; j++) {
            if (a[j] == 1 || b[t][j] == 0) continue;
            else if (a[j] != 1) {
                if (d[j] > (d[t] + b[t][j])) {
                    d[j] = d[t] + b[t][j];
                    s[i].from = t;
                }
            }
        }
        c++;
    }
    for (int i = 0; i < 4; i++)
        cout << "from node " << s[i].from << " cost is:" << d[i] << endl;
}

int main() {
    int a[4], d[4];
    for(int k = 0; k < 4; k++) d[k] = INFINITY;
    for (int i = 0; i < 4; i++) a[i] = 0;
    int b[4][4];
    for (int i = 0; i < 4; i++) {
        cout << "enter values for " << (i+1) << " row" << endl;
        for(int j = 0; j < 4; j++) cin >> b[i][j];
    }
    djikstras(a, b, d);
    return 0;
}

আউটপুট

enter values for 1 row
0 1 3 2
enter values for 2 row
2 1 3 0
enter values for 3 row
2 3 0 1
enter values for 4 row
1 3 2 0
from node 0 cost is:0
from node 0 cost is:1
from node 0 cost is:3
from node 0 cost is:2