पर केएसपीए के लिए सुझाव केएसपीए का एक कस्टम कार्यान्वयन है जिसे फिर से लिखा जाना चाहिए। वर्तमान कार्यान्वयन एक संशोधित डिजस्ट्रा के एल्गोरिदम का उपयोग करता है जिसका छद्म कोड लगभग नीचे समझाया गया है। यह आमतौर पर केएसपीए के रूप में जाना जाता है जो मुझे लगता है कि किनारे हटाने की रणनीति का उपयोग कर। (मैं ग्राफ-सिद्धांत में एक नौसिखिया हूँ)।अप्रत्यक्ष ग्राफ
Step:-1. Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2. Set k = 1
Step:-3. Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4. Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5. Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6. Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7. Add the resulting path into a temporary list of paths. Paths_List.
Step:-8. Restore the deleted edges back into the graph.
Step:-9. Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP
के रूप में मैं एल्गोरिथ्म को समझते हैं,, kth सबसे छोटा रास्ता पाने के लिए 'K-1' SPTS प्रत्येक स्रोत-गंतव्य जोड़े और 'कश्मीर -1' के बीच पाया जा सकता है किनारों एक SPT से प्रत्येक हटाया जाने वाला है प्रत्येक संयोजन के लिए एक साथ। स्पष्ट रूप से इस एल्गोरिदम में संयोजी जटिलता है और सर्वर को बड़े ग्राफ पर क्लोग करता है। लोगों ने मुझे एपस्टीन के एल्गोरिदम (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf) का सुझाव दिया। लेकिन यह श्वेत पत्र एक 'digraph' उद्धृत करता है और मुझे यह उल्लेख नहीं आया कि यह केवल digraphs के लिए काम करता है। मैं सिर्फ लोगों से पूछना चाहता था अगर किसी ने अप्रत्यक्ष ग्राफ पर इस एल्गोरिदम का उपयोग किया हो?
यदि नहीं, तो क्या अप्रत्यक्ष ग्राफ पर केएसपीए को लागू करने के लिए अच्छे एल्गोरिदम (समय-जटिलता के मामले में) हैं?
अग्रिम धन्यवाद,
अनिर्दिष्ट रेखांकन मूल रूप से हर बढ़त के साथ द्वि आलेख दोगुनी, सही कर रहे हैं? आपके द्वारा लिंक किए गए एल्गोरिदम के साथ कोई समस्या नहीं होनी चाहिए। –
हां। लेकिन अलगो पर काम करने वाले किसी ने मुझे बताया कि यह एक विशेष वितरण तकनीक का उपयोग करता है जो अप्रत्यक्ष ग्राफ पर काम नहीं कर सकता है। इसलिए, मैंने यह जांचने के बारे में सोचा कि क्या किसी ने वास्तव में इसे अप्रत्यक्ष ग्राफ पर लागू किया है। लेकिन मैं जांच करूँगा। कार्यान्वयन चल रहा है ... – Abhay
एपस्टीन एल्गोरिदम केवल विश्वकोश ग्राफ पर काम करता है। हालांकि एक अप्रत्यक्ष ग्राफ दोनों दिशाओं में किनारों के साथ एक निर्देशित ग्राफ है, लेकिन चक्र की वजह से विचलन तकनीक विफल हो जाती है। – Abhay