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

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

छोटी दूरी का पता लगाने के लिए, हम नकारात्मक भार वाले ग्राफ के लिए बेलमैन-फोर्ड जैसे अन्य एल्गोरिदम का उपयोग कर सकते हैं, सकारात्मक भार के लिए डिज्क्स्ट्रा का एल्गोरिदम भी सहायक है। यहाँ निर्देशित चक्ररहित ग्राफ के लिए, हम जटिलता कम करने के लिए टोपोलॉजिकल सॉर्टिंग तकनीक का उपयोग करेंगे।

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

इनपुट: ग्राफ का लागत मैट्रिक्स। 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ -∞ 0 आउटपुट: स्रोत शीर्ष 1 से सबसे छोटी दूरी अनंत 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] = ∞, तो           अनंत प्रदर्शित करें       अन्यथा           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 dist[nextVert] +cost[nextVert][v])dist[v] = dist[nextVert] + cost[nextVert][v];           }         }       }     for(int i = 0; i
आउटपुट
Shortest Distance From Source Vertex 1 Infinity 0 2 6 5 3