<दिव>
एन वर्टिकल और एम किनारों के साथ एक निर्देशित या अप्रत्यक्ष भारित ग्राफ दिया गया है। सभी किनारों का भार गैर-ऋणात्मक है। कुछ आरंभिक शीर्ष निर्दिष्ट किए गए हैं। आपको शीर्ष s से अन्य सभी शीर्षों तक सबसे छोटे पथों की लंबाई ज्ञात करने की आवश्यकता है, और स्वयं सबसे छोटे पथों को प्रिंट करने का तरीका भी प्रदान करें।
इस समस्या को "एकल स्रोत सबसे छोटी पथ समस्या" कहा जाता है (एकल-स्रोत लघुतम पथ समस्या)।
1-के बीएफएस के समान कार्य करता है, लेकिन के पर ध्यान दिए बिना। साथ ही, 1-के बीएफएस की तरह, यह नकारात्मक किनारों को ठीक से नहीं संभालता है
एल्गोरिदम:
दिज्क्स्त्र के एल्गोरिद्म में ही N पुनरावृत्तियां हैं। अगले पुनरावृति पर, शीर्ष V अभी तक चिह्नित नहीं किए गए शीर्षों में से इसकी सबसे छोटी दूरी के साथ, यह शीर्ष चिह्नित हो जाता है और इससे पड़ोसी शीर्षों की छूट मिलती है।
एल्गोरिदम का अंतिम स्पर्शोन्मुख व्यवहार है: O(n
2+ m)
