C++ প্রোগ্রাম: ডিকস্ট্রা অ্যালগরিদম দিয়ে ইলেকট্রিক্যাল সার্কিটের ওয়ার দৈর্ঘ্য অপ্টিমাইজেশন

এলগরিদম

ইলেকট্রিক্যাল সার্কিটে কম্পোনেন্টগুলির মধ্যে সংযোগকে একটি ওজনযুক্ত গ্রাফ (weighted graph) হিসেবে মডেল করা হয়। একটি সোর্স কম্পোনেন্ট থেকে অন্য সব কম্পোনেন্ট পর্যন্ত ন্যূনতম দূরত্ব (শর্টেস্ট পাথ) খুঁজে বের করতে ডিকস্ট্রা অ্যালগরিদম ব্যবহার করা হয়। এটি ওয়ার দৈর্ঘ্য কমিয়ে দেয়।

ডিকস্ট্রা অ্যালগরিদমের ধাপসমূহ:

সকল ভার্টেক্সের দূরত্ব INFINITY এবং ভিজিটেড false দিয়ে ইনিশিয়ালাইজ করুন।
সোর্সের দূরত্ব 0 সেট করুন।
V-1 বার লুপ চালান: প্রতিবার অনবিজিটেড ভার্টেক্সগুলির মধ্যে ন্যূনতম দূরত্ব والা বেছে নিন, তা ভিজিটেড চিহ্নিত করুন, এবং এর সা၌ súlyযুক্ত এজ দিয়ে প্রতিবেশীদের দূরত্ব আপডেট করুন (relaxation)।
সব কম্পোনেন্টের ন্যূনতম দূরত্ব প্রিন্ট করুন।

উদাহরণ কোড

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

#define N 6

int minDistance(vector<int>& dist, vector<bool>& sptSet) {
    int min = INT_MAX, min_index = -1;
    for (int v = 0; v < N; v++)
        if (!sptSet[v] && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printSolution(vector<int>& dist) {
    cout << "কম্পোনেন্ট\tসোর্স থেকে দূরত্ব\n";
    for (int i = 0; i < N; i++)
        cout << i << "\t\t" << dist[i] << "\n";
}

void optimizeWireLength(int graph[N][N], int src) {
    vector<int> dist(N, INT_MAX);
    vector<bool> sptSet(N, false);
    dist[src] = 0;

    for (int count = 0; count < N - 1; count++) {
        int u = minDistance(dist, sptSet);
        if (u == -1) break;
        sptSet[u] = true;

        for (int v = 0; v < N; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
    printSolution(dist);
}

int main() {
    int graph[N][N] = {
        {0, 0, 6, 7, 0, 4},
        {4, 0, 8, 0, 1, 2},
        {0, 9, 0, 2, 0, 4},
        {0, 0, 7, 0, 9, 5},
        {0, 1, 0, 0, 6, 7},
        {6, 7, 0, 0, 2, 3}
    };
    cout << "শুরু করার কম্পোনেন্ট (0-" << N-1 << "): ";
    int s; cin >> s;
    optimizeWireLength(graph, s);
    return 0;
}

আউটপুট উদাহরণ

ইনপুট: 4
আউটপুট:
কম্পোনেন্ট    সোর্স থেকে দূরত্ব
0               5
1               1
2               9
3               11
4               0
5               3

ব্যাখ্যা

গ্রাফের প্রতিটি নোড একটি ইলেকট্রিক্যাল কম্পোনেন্ট উপস্থাপন করে, এজের ওজন তার汉书 ওয়ারের দৈর্ঘ্য বা রেজিস্ট্যান্স। ডিকস্ট্রা অ্যালগরিদম সোর্স থেকে সব কম্পোনেন্ট পর্যন্ত ন্যূনতম পাথ দিয়ে মোট ওয়ার দৈর্ঘ্য কমাতে সাহায্য করে।