निर्देशित चक्ररहित ग्राफ में सबसे लंबा पथ

एक भारित निर्देशित चक्ररहित ग्राफ दिया गया है। एक स्रोत शीर्ष भी प्रदान किया गया है। अब हमें ग्राफ में प्रारंभिक नोड से अन्य सभी शीर्षों तक की सबसे लंबी दूरी खोजनी है।

हमें नोड्स को टोपोलॉजिकल सॉर्टिंग तकनीक में क्रमबद्ध करने की आवश्यकता है, और टोपोलॉजिकल सॉर्ट के बाद परिणाम को स्टैक में संग्रहीत किया जाता है। उसके बाद स्टैक से बार-बार पॉप करके प्रत्येक शीर्ष के लिए सबसे लंबी दूरी खोजने का प्रयास करें।

इनपुट और आउटपुट

इनपुट: ग्राफ का लागत मैट्रिक्स। 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ -∞ 0 आउटपुट: स्रोत शीर्ष 1 से सबसे लंबी दूरी अनंत 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] = -∞, तो           अनंत प्रदर्शित करें       अन्यथा           dist[i] प्रदर्शित करें     किया अंत

उदाहरण

#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
आउटपुट
Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10