এই সমস্যায়, একটি যাত্রায় N সংখ্যক স্টপেজ রয়েছে। যানটি ০ নম্বর স্টপেজ থেকে N-1 নম্বর স্টপেজ পর্যন্ত যাত্রা শুরু করে। একটি টেবিলে সব জোড়া স্টেশনের টিকেট খরচ দেওয়া আছে। আমাদের দেওয়া খরচগুলো ব্যবহার করে ডেস্টিনেশনে পৌঁছাতে ন্যূনতম খরচ বের করতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: যাত্রার কস্ট ম্যাট্রিক্স। 0 15 80 90 ∞ 0 40 50 ∞ ∞ 0 70 ∞ ∞ ∞ 0 আউটপুট: ন্যূনতম খরচ ৬৫। প্রথমে ০ থেকে ১ নম্বর ডেস্টিনেশনে যান (খরচ ১৫), তারপর ১ থেকে ৪ (খরচ ৫০)। মোট খরচ ৬৫।
এলগরিদম
findMinCost(cost)
ইনপুট: প্রতিটি সোর্স থেকে প্রতিটি ডেস্টিনেশনের কস্ট ম্যাট্রিক্স।
আউটপুট: ডেস্টিনেশনে পৌঁছাতে ন্যূনতম খরচ বের করুন।
শুরু
costLoc নামে একটি অ্যারে সংজ্ঞায়িত করুন, যার আকার লোকেশন সংখ্যার সমান,
costLoc কে ∞ দিয়ে পূরন করুন।
n := লোকেশন সংখ্যা
costLoc[0] := 0
প্রতিটি সোর্স i থেকে প্রতিটি ডেস্টিনেশন j এর জন্য, করুন
যদি costLoc[j] > costLoc[i] + cost[i, j], তবে
costLoc[j] := costLoc[i] + cost[i, j]
শেষ লুপ
return costLoc[n-1]
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#define INF INT_MAX
#define NODE 4
using namespace std;
int cost[NODE][NODE] = {
{0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
int findMinCost() {
// ডেস্টিনেশনে পৌঁছাতে ন্যূনতম সম্ভাব্য খরচ খুঁজে বের করুন
int costStation[NODE]; // ০ থেকে যেকোনো স্টেশনে পৌঁছানোর খরচ স্টোর করুন
for (int i = 0; i < NODE; i++)
costStation[i] = INF; // প্রাথমিকভাবে সব অনন্ত
costStation[0] = 0; // স্টেশন ০-এর খরচ ০ কারণ এটি শুরুর পয়েন্ট
for (int i = 0; i < NODE; i++)
for (int j = i+1; j < NODE; j++)
if (costStation[j] > costStation[i] + cost[i][j]) // ইন্টারমিডিয়েট স্টেশন খুঁজে বের করুন ন্যূনতম খরচের জন্য
costStation[j] = costStation[i] + cost[i][j];
return costStation[NODE-1];
}
int main() {
cout << "The Minimum cost to reach station " << NODE << " is " << findMinCost() << endl;
return 0;
}
আউটপুট
The Minimum cost to reach station 4 is 65
