একটি ওজনযুক্ত ডায়রেক্টেড অসাইক্লিক গ্রাফ (DAG) দেওয়া আছে। একটি সোর্স ভার্টেক্সও প্রদত্ত। এখন আমাদের কাজ হলো গ্রাফের সকল অন্যান্য ভার্টেক্স থেকে শুরুর নোড পর্যন্ত শর্টেস্ট দূরত্ব খুঁজে বের করা।
নেগেটিভ ওজনযুক্ত গ্রাফের জন্য ছোট দূরত্ব শনাক্ত করতে বেলম্যান-ফোর্ড অ্যালগরিদম ব্যবহার করা যায়, পজিটিভ ওজনের জন্য ডিজ্কস্ট্রার অ্যালগরিদমও সাহায্যকর। কিন্তু এখানে ডায়রেক্টেড অসাইক্লিক গ্রাফের জন্য টপোলজিক্যাল সোর্টিং টেকনিক ব্যবহার করা হবে যাতে জটিলতা কম যায়।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের কস্ট ম্যাট্রিক্স। 0 5 3 ∞ ∞ ∞ ∞ 0 2 6 ∞ ∞ ∞ ∞ 0 7 4 2 ∞ ∞ ∞ 0 -1 1 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ ∞ ∞ 0 আউটপুট: সোর্স ভার্টেক্স ১ থেকে শর্টেস্ট দূরত্ব Infinity 0 2 6 5 3
এলগরিদম
topoSort(u, visited, stack)
ইনপুট: শুরুর নোড u, ট্র্যাক রাখতে ভিজিটেড লিস্ট, স্ট্যাক।
আউটপুট: নোডগুলোকে টপোলজিক্যালভাবে সর্ট করুন।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সংযুক্ত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
topoSort(v, visited, stack)
শেষ লুপ
u কে স্ট্যাকে পুশ করুন
শেষ
shortestPath(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 shortestPath(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 << "Shortest Distance From Source Vertex " << start << endl;
shortestPath(start);
}
আউটপুট
Shortest Distance From Source Vertex 1 Infinity 0 2 6 5 3
