डाइक्स्ट्रा एल्गोरिदम
शुरुआत से लक्ष्य तक सबसे सस्ता रास्ता ढूँढता है। यह हमेशा प्राथमिकता कतार में इंतज़ार कर रही सबसे सस्ती जगह लेता है, इसलिए लागत शुरुआत से बाढ़ की तरह फैलती है।
- समय O((V + E) log V)
- मेमोरी O(V)
- प्राथमिकता कतार इस्तेमाल करता है
इनका मतलब क्या है?
- लागत: एक चाल की कीमत। भूलभुलैया में ज़मीन 1, कीचड़ 3 और पानी 9; ग्राफ़ में किनारे पर लिखी संख्या।
- प्राथमिकता कतार: ऐसी कतार जिसमें पहले आने वाला नहीं, सबसे सस्ता पहले जाता है।
- अनुमान (h): बची हुई लागत का अंदाज़ा। A* तभी सटीक रहता है जब यह कभी ज़्यादा न हो।
- किनारे को ढीला करना: जाँचना कि मौजूदा जगह से होकर जाने पर पड़ोसी की लागत कम होती है या नहीं, और हो तो उसे अपनाना।
- कतार में
- मौजूदा
- पूरा
- सबसे सस्ता रास्ता
- ज़मीन · 1
- कीचड़ · 3
- पानी · 9
- दीवार
नया: A1 से शुरुआत, लागत 0। कतार में यही अकेला है।
स्पेस: चलाएं या रोकें। बाएं और दाएं ऐरो: चरण दर चरण। Home और End: सीधे जाएं।
इसे आज़माएं: दलदल चुनें। सबसे सस्ता रास्ता पूरे कीचड़ के चारों ओर घूमकर जाता है: सीधी रेखा से दोगुनी चालें, फिर भी सस्ता (36 के मुकाबले 34)।
यह कैसे काम करता है
हर जगह को एक लागत मिलती है: शुरुआत को 0, बाकी को अनंत। डाइक्स्ट्रा पहुँची हुई जगहों को प्राथमिकता कतार में रखता है और हमेशा सबसे सस्ती लेता है। तब उसकी लागत पक्की हो जाती है, क्योंकि वहाँ तक कोई भी दूसरा रास्ता कम से कम उतनी ही महँगी जगह से होकर जाएगा। फिर वह हर पड़ोसी को देखता है: अगर अभी ली गई जगह से होकर जाना पड़ोसी की अब तक की लागत से सस्ता है, तो पड़ोसी को नई लागत मिलती है और वह याद रखता है कि कहाँ से आया। लक्ष्य लेने के बाद ये कड़ियाँ सबसे सस्ते रास्ते से वापस ले जाती हैं।
यह कब सही विकल्प है
डाइक्स्ट्रा तब काम आता है जब चालों की लागत अलग-अलग हो और कोई भी शून्य से कम न हो: सड़क नक्शे और नेविगेशन, नेटवर्क रूटिंग, सबसे सस्ती उड़ान जोड़ी। अगर हर चाल की लागत बराबर है, तो BFS वही जवाब आसानी से देता है। ऋणात्मक लागत में डाइक्स्ट्रा गलत हो सकता है; उनके लिए बेलमैन–फ़ोर्ड है।