दिज्क्स्ट्रा: पाथ रिकवरी
Problem
आपको एक निर्देशित भारित ग्राफ दिया जाता है। एक दिए गए शीर्ष से दूसरे तक का सबसे छोटा रास्ता खोजें।
इनपुट
पहली पंक्ति में तीन संख्याएँ होती हैं: N, S और F (1≤N≤100, 1≤S, F≤N), जहाँ N – ग्राफ़ शीर्षों की संख्या, S – आरंभिक शीर्ष, और F – अंतिम। अगली एन पंक्तियों में, प्रत्येक संख्या एन संख्या दर्ज करें, 100 से अधिक नहीं, – ग्राफ़ आसन्न मैट्रिक्स, जहाँ -1 का अर्थ है शीर्षों के बीच कोई किनारा नहीं, और कोई भी गैर-ऋणात्मक संख्या – दिए गए वजन के किनारे की उपस्थिति। मैट्रिक्स के मुख्य विकर्ण पर शून्य लिखे जाते हैं।
आउटपुट
सबसे छोटे पथों में से किसी एक (किसी भी) के सभी शीर्षों को क्रमिक रूप से प्रदर्शित करना आवश्यक है, या निर्दिष्ट शीर्षों के बीच कोई पथ न होने पर एक संख्या -1 प्रदर्शित करना आवश्यक है।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
3 2 1
0 1 1
4 0 1
2 1 0
2 3 1 |