একটি ডায়রেক্টেড গ্রাফ দেওয়া আছে প্রতিটি ভার্টেক্স জোড়ার মধ্যে ওজন সহ, এবং দুটি ভার্টেক্স u এবং vও প্রদত্ত। আমাদের কাজ হলো ভার্টেক্স u থেকে ভার্টেক্স v-এ ঠিক k সংখ্যক এজ দিয়ে শর্টেস্ট দূরত্ব খুঁজে বের করা।
এই সমস্যা সমাধান করতে, আমরা ভার্টেক্স u থেকে শুরু করে সব সন্নিহিত ভার্টেক্সে যাব এবং k মানকে k-1 করে রিকারসিভভাবে সন্নিহিত ভার্টেক্সের জন্য কল করব।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের কস্ট ম্যাট্রিক্স। 0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 আউটপুট: শর্টেস্ট পাথের ওজন: 9
এলগরিদম
shortKEdgePath(u, v, edge)
ইনপুট: ভার্টেক্স u এবং v, এবং এজের সংখ্যা।
আউটপুট: শর্টেস্ট পাথের দূরত্ব।
শুরু
যদি edge = 0 এবং u = v, তবে
return 0
যদি edge = 1 এবং cost[u, v] ≠ ∞, তবে
return cost[u, v]
যদি edge <= 0, তবে
return ∞
shortPath := ∞ সেট করুন
সব ভার্টেক্স i এর জন্য, করুন
যদি cost[u, i] ≠ ∞ এবং u ≠ i এবং v ≠ i, তবে
tempRes := shortKEdgePath(i, v, edge - 1)
যদি tempRes ≠ ∞, তবে
shortPath = shortPath এবং (cost[u,i] + tempRes)-এর ন্যূনতম
শর্ত শেষ
শেষ লুপ
return shortPath
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#define NODE 4
#define INF INT_MAX
using namespace std;
int cost[NODE][NODE] = {
{0, 10, 3, 2},
{INF, 0, INF, 7},
{INF, INF, 0, 6},
{INF, INF, INF, 0}
};
int minimum(int a, int b) {
return (a < b) ? a : b;
}
int shortKEdgePath(int u, int v, int edge) {
if (edge == 0 && u == v) // যখন ০ এজ, কোনো পথ নেই
return 0;
if (edge == 1 && cost[u][v] != INF) // যখন শুধু একটি এজ, এবং (u,v) বৈধ
return cost[u][v];
if (edge <= 0) // যখন এজ নেগেটিভ, অনন্ত সমাধান
return INF;
int shortPath = INF;
for (int i = 0; i < NODE; i++) {
// u-র সাথে সন্নিহিত সব ভার্টেক্স i এর জন্য
if (cost[u][i] != INF && u != i && v != i) {
int tempRes = shortKEdgePath(i, v, edge-1);
if (tempRes != INF)
shortPath = minimum(shortPath, cost[u][i] + tempRes);
}
}
return shortPath;
}
int main() {
int src = 0, dest = 3, k = 2;
cout << "Weight of the shortest path is " << shortKEdgePath(src, dest, k);
}
আউটপুট
Weight of the shortest path is 9
