C++-এ জনসন অ্যালগরিদম (Johnson's Algorithm) ইমপ্লিমেন্টেশন

এখানে আমরা দুটি ভার্টেক্সের মধ্যে সবচেয়ে ছোট পাথ (shortest path) বের করার জন্য জনসন অ্যালগরিদম (Johnson's Algorithm) দেখব।

গ্রাফটি এখানে দেওয়া আছে। এজগুলোর মধ্যে সবচেয়ে ছোট পাথ নিচের মতো। এই প্রোগ্রাম ভার্টেক্স সংখ্যা, এজ সংখ্যা, এবং তাদের কস্ট সহ এজগুলো ইনপুট হিসেবে নেবে।

ইনপুট - ভার্টেক্স: ৩

এজ: ৫

এজ ও কস্ট:

1 2 8

2 1 12

1 3 22

3 1 6

2 3 4

আউটপুট - গ্রাফের দূরত্ব ম্যাট্রিক্স (distance matrix)।

অ্যালগরিদম

johnsonAlgorithm(cost)

ইনপুট - দেওয়া গ্রাফের কস্ট ম্যাট্রিক্স।

আউটপুট - যেকোনো ভার্টেক্স থেকে যেকোনো ভার্টেক্সে সবচেয়ে ছোট পাথের জন্য ম্যাট্রিক্স।

শুরু
  'A' নামক অন্য একটি ম্যাট্রিক্স তৈরি করুন cost ম্যাট্রিক্সের মত, যদি i-তম সারি এবং j-তম কলামের মধ্যে কোনো এজ নেই থাকে, তবে A[i,j]-তে infinity রাখুন
  k := 1 থেকে n পর্যন্ত, করুন
    i := 1 থেকে n পর্যন্ত, করুন
      j := 1 থেকে n পর্যন্ত, করুন
        A[i, j] = A[i, j] এবং (A[i, k] + A[k, j]) এর মধ্যে ন্যূনতম
      শেষ করুন
    শেষ করুন
  শেষ করুন
  বর্তমান A ম্যাট্রিক্স প্রদর্শন করুন
শেষ

উদাহরণ কোড

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

int min(int a, int b);
int cost[10][10], adj[10][10];

inline int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int vert, edge, i, j, k, c;
    cout << "Enter no of vertices: ";
    cin >> vert;
    cout << "Enter no of edges: ";
    cin >> edge;
    cout << "Enter the EDGE Costs:\n";
    
    for (k = 1; k <= edge; k++) { // ইনপুট নিয়ে adj এবং cost ম্যাট্রিক্সে স্টোর
        cin >> i >> j >> c;
        adj[i][j] = cost[i][j] = c;
    }
    
    for (i = 1; i <= vert; i++)
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] == 0 && i != j)
                adj[i][j] = INF; // এজ না থাকলে infinity
        }
    
    for (k = 1; k <= vert; k++)
        for (i = 1; i <= vert; i++)
            for (j = 1; j <= vert; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); // k দিয়ে i থেকে j-এর ন্যূনতম পাথ
    
    cout << "Resultant adj matrix\n";
    for (i = 1; i <= vert; i++) {
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] != INF)
                cout << adj[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

আউটপুট

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0