शहरहरूबीचको सबैभन्दा छोटो सडक
काठमाडौँ वा पोखराबाट अर्को शहरसम्म सडकबाट सबैभन्दा छोटो बाटो खोज्नुहोस्। Dijkstra को algorithm ले सबैभन्दा नजिकको शहर पहिले पक्का गरेको, त्यहाँबाट जाने सडक प्रयास गरेको, र हरेक शहरसम्म भेटेको सबैभन्दा छोटो दूरी राखेको हेर्नुहोस्।
मूल अवधारणा
Dijkstra को algorithm ले शहरहरूलाई सुरुबाटको दूरीको क्रममा पक्का गर्छ; पक्का भएको हरेक शहरको दूरी अन्तिम हो, र त्यहाँबाट जाने सडकले अरू शहरको दूरी छोटो मात्र बनाउन सक्छन्
पाठ: Algorithm
सडकले जोडिएका शहरहरूको नक्सा एउटा graph हो: शहर यसका node र सडक यसका edge, हरेकको लम्बाइसहित। फोनका नक्साले Edsger Dijkstra को विचारले सबैभन्दा छोटो बाटो खोज्छन्। सुरु 0 km टाढा हुन्छ र अरू हरेक शहर ∞ (अझै नपुगेको)। हरेक चरणमा प्रोग्रामले थाहा भएको दूरी सबैभन्दा सानो भएको पक्का नभएको शहर पक्का गर्छ: त्यो दूरी कहिल्यै छोटो हुन सक्दैन, किनकि अरू हरेक बाटो पहिले नै टाढा भएको शहर भएर जानुपर्थ्यो। अनि यसले पक्का भएको शहरबाट जाने हरेक सडक प्रयास गर्छ: त्यहाँ भएर जाँदा छिमेकीको दूरी थाहा भएकोभन्दा छोटो हुन्छ भने छोटोले पुरानोलाई बदल्छ। गन्तव्य पक्का भएपछि यसको दूरी सबैभन्दा छोटो हुन्छ, र त्यो दूरी दिने शहरहरू पछाडि पछ्याउँदा बाटो देखिन्छ। यो Lab का दूरी नक्साका लागि सरल बनाइएका, rounded सडक दूरी हुन्।
के सिक्नुहुनेछ
- सडकको नक्सालाई node र लम्बाइ भएका edge को graph का रूपमा वर्णन गर्नुहोस्।
- Dijkstra को algorithm trace गर्नुहोस्: सबैभन्दा नजिकको शहर पक्का गर्ने, अनि यसका सडक प्रयास गर्ने।
- पक्का भएको शहरको दूरी किन अन्तिम हुन्छ, व्याख्या गर्नुहोस्।
- सबैभन्दा कम सडक भएको बाटो सधैँ सबैभन्दा छोटो हुँदैन भनेर देखाउनुहोस्।
सुरु गर्नुअघि
- दूरी जोड्न र कुन सानो हो तुलना गर्न आउनुपर्छ।
सामग्री
- नेपालको नक्सा, छ भने
उपकरण
- केही पनि चाहिँदैन
विधि
- काठमाडौँबाट पोखरासम्मको सबैभन्दा छोटो बाटो खोज्नुहोस्।
- हरेक चरण Step गर्दै काठमाडौँबाट बुटवलसम्मको सबैभन्दा छोटो बाटो खोज्नुहोस्।
- अरू शहर प्रयास गर्नुहोस्, र पोखराबाट सुरु गर्नुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।
यो Simulation लाई कसरी सरल बनाइएको छ
- सडक दूरी rounded र सरल बनाइएका छन्: हरेक सडकले दुई शहरलाई सिधै जोड्छ, र सडक दुवैतिर चल्छन्।