একটি ওজনযুক্ত ডায়রেক্টেড অসাইক্লিক গ্রাফ দেওয়া আছে। একটি সোর্স ভার্টেক্সও প্রদত্ত। এখন আমাদের কাজ হলো গ্রাফের সকল অন্যান্য ভার্টেক্স থেকে শুরুর নোড পর্যন্ত লংগেস্ট (সর্বোচ্চ) দূরত্ব খুঁজে বের করা।
নোডগুলোকে টপোলজিক্যাল সোর্টিং টেকনিক দিয়ে সর্ট করতে হবে, এবং টপোলজিক্যাল সোর্টের ফলাফল একটি স্ট্যাকে সংরক্ষণ করতে হবে। এরপর স্ট্যাক থেকে বারবার পপ করে প্রতিটি ভার্টেক্সের জন্য লংগেস্ট দূরত্ব খুঁজে বের করতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের কস্ট ম্যাট্রিক্স। 0 5 3 ∞ ∞ ∞ ∞ 0 2 6 ∞ ∞ ∞ ∞ 0 7 4 2 ∞ ∞ ∞ 0 -1 1 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ ∞ ∞ 0 আউটপুট: সোর্স ভার্টেক্স ১ থেকে লংগেস্ট দূরত্ব Infinity 0 2 9 8 10
এলগরিদম
topoSort(u, visited, stack)
ইনপুট: শুরুর নোড u, ট্র্যাক রাখতে ভিজিটেড লিস্ট, স্ট্যাক।
আউটপুট: নোডগুলোকে টপোলজিক্যালভাবে সর্ট করুন।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সংযুক্ত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
topoSort(v, visited, stack)
শেষ লুপ
u কে স্ট্যাকে পুশ করুন
শেষ
longestPath(start)
ইনপুট: শুরুর নোড।
আউটপুট: শুরুর নোড থেকে সব ভার্টেক্সের লংগেস্ট দূরত্বের লিস্ট।
শুরু
প্রাথমিকভাবে সব নোডকে অনভিজিটেড করুন
গ্রাফের প্রতিটি নোড i এর জন্য, করুন
যদি i ভিজিটেড না থাকে, তবে
topoSort(i, visited, stack)
শেষ লুপ
সব ভার্টেক্সের দূরত্ব -∞ করুন
dist[start] := 0
যতক্ষণ স্ট্যাক খালি নয়, করুন
স্ট্যাক আইটেম পপ করুন এবং nextVert-এ নিন
যদি dist[nextVert] ≠ -∞, তবে
nextVert-র সাথে সংলগ্ন প্রতিটি ভার্টেক্স v এর জন্য, করুন
যদি cost[nextVert, v] ≠ -∞, তবে
যদি dist[v] < dist[nextVert] + cost[nextVert, v], তবে
dist[v] := dist[nextVert] + cost[nextVert, v]
শেষ লুপ
শেষ শর্ত
শেষ লুপ
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
যদি dist[i] = -∞, তবে
Infinity প্রদর্শন করুন
অন্যথায়
dist[i] প্রদর্শন করুন
শেষ লুপ
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <stack>
#define NODE 6
#define INF -9999
using namespace std;
int cost[NODE][NODE] = {
{0, 5, 3, INF, INF, INF},
{INF, 0, 2, 6, INF, INF},
{INF, INF, 0, 7, 4, 2},
{INF, INF, INF, 0, -1, 1},
{INF, INF, INF, INF, 0, -2},
{INF, INF, INF, INF, INF, 0}
};
void topoSort(int u, bool visited[], stack<int> &stk) {
visited[u] = true; // নোড v কে ভিজিটেড হিসেবে সেট করুন
for(int v = 0; v < NODE; v++) {
if(cost[u][v]) { // u-র সাথে সংলগ্ন সব ভার্টেক্স v এর জন্য
if(!visited[v])
topoSort(v, visited, stk);
}
}
stk.push(u); // শুরুর ভার্টেক্সকে স্ট্যাকে পুশ করুন
}
void longestPath(int start) {
stack<int> stk;
int dist[NODE];
bool vis[NODE];
for(int i = 0; i < NODE; i++)
vis[i] = false; // প্রথমে সব নোডকে অনভিজিটেড করুন
for(int i = 0; i < NODE; i++)
if(!vis[i])
topoSort(i, vis, stk); // ভার্টেক্সের জন্য টপোলজিক্যাল সোর্ট
for(int i = 0; i < NODE; i++)
dist[i] = INF; // প্রাথমিকভাবে সব দূরত্ব -অনন্ত
dist[start] = 0; // শুরুর ভার্টেক্সের দূরত্ব ০
while(!stk.empty()) {
// যখন স্ট্যাকে উপাদান থাকে, টপোলজিক্যাল ক্রমে প্রসেস করুন
int nextVert = stk.top(); stk.pop();
if(dist[nextVert] != INF) {
for(int v = 0; v < NODE; v++) {
if(cost[nextVert][v] && cost[nextVert][v] != INF) {
if(dist[v] < dist[nextVert] + cost[nextVert][v])
dist[v] = dist[nextVert] + cost[nextVert][v];
}
}
}
}
for(int i = 0; i < NODE; i++)
(dist[i] == INF) ? cout << "Infinity " : cout << dist[i] << " ";
}
int main() {
int start = 1;
cout << "Longest Distance From Source Vertex " << start << endl;
longestPath(start);
}
আউটপুট
Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10
