डेक्स्ट्रा एल्गोरिदम र यसको कार्यान्वयन

गणित विज्ञान र कम्प्युटर विज्ञान मा एक अलग दिशा हो, ग्राफ को सिद्धान्त भनिन्छ। यसको ढाँचा भित्र, विभिन्न कार्यहरू सेट र समाधान गरिएका छन्, उदाहरणका लागि, ठाडो बीचको छोटो बाटो पत्ता लगाउन। गणितज्ञहरु बीच यस समस्या को सुलझाने को लागि एक सबै भन्दा साधारण तरीकाहरु Dijkstra एल्गोरिथ्म लामो छ।

गणित ग्राफिक के हो?

यो मानिन्छ कि ग्राफ को अवधारणा को अठारहौं शताब्दी लियोनार्ड इलर द्वारा पेश गरिएको थियो। यो उनी को थिए जसले यस सिद्धान्त को शास्त्रीय समस्याहरु को एक सूत्र र समाधान को हल - कोइन्ग्सबर्ग को सात पुलों को बारे मा। यस सिद्धान्त को वस्तु को व्याख्या गर्न को लागि, प्रायः विभिन्न शहरहरु को बीच आंदोलन को रूप मा एक समान को रूप मा प्रयोग गर्दछ। त्यसपछि विमानमा ग्राफले मार्गहरूको सम्पूर्ण योजनालाई प्रतिनिधित्व गर्दछ, जहाँ ठाडो विशिष्ट बिन्दुहरू हो (उदाहरणको लागि, शहरहरू), र किनारहरू एक ठाडोबाट अर्को बाटोहरू (शहरहरू बीचको सडकमा अनुरूप)। Dijkstra को एल्गोरिथ्म, अन्य तरिकाहरु को अतिरिक्त, यस प्रश्न को एक समाधान दे सकते हो।

सबभन्दा छोटो बाटो खोज्दै

ग्राफिक्स को एक मानक समस्या को एक समस्या छ जसमा दुई बिन्दुहरु बीच लागत-इष्टतम मार्ग निर्धारित गर्न आवश्यक छ। यो ग्राफमा समाधानको लागि विमानमा कम गर्न सकिन्छ, जसमा ठाडो - शहरहरू - रिब्सद्वारा जोडिएको छ, जुन सम्भावित सडकहरू प्रतिनिधित्व गर्दछ। र प्रत्येक सडकको आफ्नै लम्बाई छ, त्यसकारण, यो यात्रा पछि निश्चित रकम खर्च गर्न हुनेछ। यो योग ग्राफ मा एक किनारा को वजन को बराबर छ। त्यसोभए व्यवहारमा समस्या निम्नानुसार तैयार गर्न सकिन्छ: कसरी एक शहरबाट अर्को मार्गमा प्रशस्त गर्न, कोषमा न्यूनतम रकममा खर्च गर्न।

समाधानहरू

यस समस्याको समाधान गर्न, केहि एल्गोरिदमहरू आविष्कार गरियो, जुन वैज्ञानिक संसारमा व्यापक रूपमा चिनिन्थ्यो। उदाहरणको लागि, फ्लोइड-वर्सहेल एल्गोरिदम, फोर्ड-बेल्ल्मन एल्गोरिदम। Dijkstra एल्गोरिथ्म समाधान खोजको एक क्लासिक तरिका हो। यो पनि वजन (प्रत्येक किनाराको ज्ञात वजन) को लागी प्रयोग गर्न सकिन्छ, र फोटाको लागि। अन्तिम बाटो पत्ता लगाउन, तपाइँ केहि कदमहरू गर्न आवश्यक छ।

डिजास्टका एल्गोरिथ्म

यस विधिको अर्थ यो हो कि सबै ठाडो बाईपास गरिएको छ, दिइएका एक साथ शुरुवात, प्रत्येक एक निश्चित मानको साथ एक लेबल दिइन्छ। त्यसपछि परिणामले ती ठाँउहरू समावेश गर्दछ जसको लेबल कम से कम छ। पहिलो चरणमा, मूल ठाडोले लेबलको साथ एक लेबल निर्दिष्ट गर्दछ। त्यसपछि सबै निम्न ठाडो रूपमा मानिन्छ, यो हो, जुन मूलबाट पहुँच गर्न सकिन्छ। तिनीहरू लेबलहरू नियुक्त गरिएका छन् जसको मूल्य स्रोतको योग र पथको वजनको रूपमा परिभाषित गरिएको छ। अर्को चरणको ठाडोबाट, एक छानिएको छ कि लेबलको सबै भन्दा सानो मूल्य, र सबै उर्वरहरू जुन मध्यवर्ती ठाडो प्रयोग गरी ट्रान्सफर गर्न सकिन्छ अध्ययन गरिन्छ। लेबलको नयाँ मान परिभाषित गरिएको छ, स्रोत ठाडोको लेबल र पथको वजनको बराबर। यदि परिणाम मान ठाडो लेबल भन्दा कम छ भने, त्यसपछि लेबल परिवर्तन गर्दछ। अन्यथा, मूल मूल्य बनी रहन्छ। यस अवस्थामा, एक अलग array मा, जसको आयाम ग्राफ को ठाडो संख्या को बराबर छ, अनुकूलन को परिणाम संरक्षित छ, जसको साथ पथ को निर्धारण गरिन्छ। Dijkstra एलगोरिदमको रूपमा यस्तो तरिकालाई लागू गर्न, पास्कल धेरै सुविधाजनक उपकरण प्रदान गर्दछ। एल्गोरिथ्मले फाइदा पाउदछ कि यो सजिलै प्रयोगको कार्यक्रमको रूपमा सानो आकारको रूपमा प्रयोग गर्न सकिन्छ। यस्तो सफ्टवेयर उत्पादनका उदाहरणहरू इन्टरनेटमा फेला पार्न सजिलो छ।

इष्टतम पथ फेला पार्न समस्या समाधान गर्न विभिन्न माध्यमहरू प्रयोग गर्न सकिन्छ। Dijkstra को एल्गोरिदम जस्तै एक समाधान को लागि, डेल्फी मूल डेटा इनपुट र अंतिम परिणाम आउटपुट को लागि एक दृश्य सुविधाजनक फारम बनाइएगा।