একটি নির্দেশিত গ্রাফ প্রতিটি জোড়া শীর্ষবিন্দুর মধ্যে ওজন সহ দেওয়া হয়েছে, এবং দুটি শীর্ষবিন্দু u এবং vও দেওয়া হয়েছে৷ আমাদের কাজ হল প্রান্তের ঠিক k সংখ্যা সহ শীর্ষবিন্দু u থেকে শীর্ষবিন্দু v পর্যন্ত সবচেয়ে কম দূরত্ব খুঁজে বের করা।
এই সমস্যাটি সমাধান করার জন্য, আমরা vertex u থেকে শুরু করব এবং সমস্ত সন্নিহিত শীর্ষবিন্দুতে যাব এবং k - 1 হিসাবে k মান ব্যবহার করে সন্নিহিত শীর্ষবিন্দুগুলির জন্য পুনরাবৃত্তি করব।
ইনপুট এবং আউটপুট
Input: The cost matrix of the graph. 0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 Output: Weight of the shortest path is 9
অ্যালগরিদম
shortKEdgePath(u, v, edge)
ইনপুট - ভার্টেক্স u এবং v, এবং বেশ কয়েকটি প্রান্ত।
আউটপুট - সংক্ষিপ্ততম পথের দূরত্ব।
Begin if edge = 0 and u = v, then return 0 if edge = 1 and cost[u, v] ≠ ∞, then return cost[u, v] if edge <= 0, then return ∞ set shortPath := ∞ for all vertices i, do if cost[u, i] ≠ ∞ and u ≠ i and v ≠ i, then tempRes := shortKEdgePath(i, v, edge - 1) if tempRes ≠ ∞, then shortPath = minimum of shortPath and (cost[u,i]+tempRes done return shortPath End
উদাহরণ
#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) //when 0 edge, no path is present
return 0;
if (edge == 1 && cost[u][v] != INF) //when only one edge, and (u,v) is valid
return cost[u][v];
if (edge <= 0) //when edge is -ve, there are infinity solution
return INF;
int shortPath = INF;
for (int i = 0; i < NODE; i++) { //for all vertices i, adjacent to u
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
