112गणित · विश्वविद्यालय गणित · ग्राफ सिद्धांत

सबसे छोटा पथ: 15 किनारे

fx-50FH II · CMPLX · 547 bytes

अधिकतम दस शीर्षों और 15 किनारों वाले अदिश नेटवर्क में न्यूनतम लागत का एक पथ खोजें; पहले क्रम से शीर्ष, फिर कुल लागत दिखती है।

  • 547 बाइट
  • CMPLX मोड
01

हल किए गए उदाहरण

उदाहरण 1

विश्वविद्यालय संक्रिया अनुसंधान का मौलिक अभ्यास: संग्रहालय रोबोट क्रमांकित कक्षों में चलता है। रास्ते दोनों दिशाओं में हैं और लागत मिनट है। 2 से 6 तक न्यूनतम समय का पथ और कुल समय निकालें।
सभी दिए किनारे अदिश हैं; न दिए संपर्क नहीं हैं। सूची (a–b: लागत): 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12

उत्तर
2 → 3 → 4 → 6; कुल लागत 4+2+3=9 min
मानक हल (कैलकुलेटर के बिना)
  1. S से Dijkstra लगाएँ। u नया निश्चित शीर्ष, d(v) अद्यतन अस्थायी दूरी और ∞ अभी अप्राप्य है।
  2. u=2, d(2)=0; d(1)=7, d(3)=4
  3. u=3, d(3)=4; d(4)=6, d(5)=12
  4. u=4, d(4)=6; d(6)=9
  5. u=1, d(1)=7; ∅
  6. u=6, d(6)=9; d(5)=11
  7. पूर्ववर्ती से पथ निकालकर लागत सीधे जोड़ें: 2 → 3 → 4 → 6; कुल लागत 4+2+3=9 min
कैलकुलेटर पर करें

उदाहरण 2

विश्वविद्यालय संक्रिया अनुसंधान का मौलिक अभ्यास: प्रदर्शनी शटल नेटवर्क में पूर्णांक किराया इकाइयाँ हैं। 7–8 का संपर्क निःशुल्क है, लागत ठीक 0। 7 से 2 तक न्यूनतम किराया पथ और कुल किराया निकालें।
सभी दिए किनारे अदिश हैं; न दिए संपर्क नहीं हैं। सूची (a–b: लागत): 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1

उत्तर
7 → 8 → 9 → 1 → 2; कुल लागत 0+3+1+2=6
मानक हल (कैलकुलेटर के बिना)
  1. S से Dijkstra लगाएँ। u नया निश्चित शीर्ष, d(v) अद्यतन अस्थायी दूरी और ∞ अभी अप्राप्य है।
  2. u=7, d(7)=0; d(1)=9, d(8)=0
  3. u=8, d(8)=0; d(2)=10, d(9)=3
  4. u=9, d(9)=3; d(1)=4, d(2)=7
  5. u=1, d(1)=4; d(2)=6
  6. u=2, d(2)=6; ∅
  7. पूर्ववर्ती से पथ निकालकर लागत सीधे जोड़ें: 7 → 8 → 9 → 1 → 2; कुल लागत 0+3+1+2=6
कैलकुलेटर पर करें

उदाहरण 3

विश्वविद्यालय संक्रिया अनुसंधान का मौलिक अभ्यास: प्रशिक्षण संचार नेटवर्क दस आभासी टर्मिनल जोड़ता है। हर द्विदिश संपर्क की संचरण लागत निश्चित पूर्णांक है। अंतिम संपर्क सहित सभी 15 संपर्क सूची के क्रम में दें और 1 से 10 का न्यूनतम लागत पथ तथा कुल लागत निकालें।
सभी दिए किनारे अदिश हैं; न दिए संपर्क नहीं हैं। सूची (a–b: लागत): 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1

उत्तर
1 → 2 → 9 → 10; कुल लागत 5+1+4=10
मानक हल (कैलकुलेटर के बिना)
  1. S से Dijkstra लगाएँ। u नया निश्चित शीर्ष, d(v) अद्यतन अस्थायी दूरी और ∞ अभी अप्राप्य है।
  2. u=1, d(1)=0; d(2)=5, d(6)=9
  3. u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
  4. u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
  5. u=6, d(6)=9; d(5)=12
  6. u=10, d(10)=10; ∅
  7. पूर्ववर्ती से पथ निकालकर लागत सीधे जोड़ें: 1 → 2 → 9 → 10; कुल लागत 5+1+4=10
कैलकुलेटर पर करें
02

कब उपयोग करें

विश्वविद्यालय गणित · संक्रिया अनुसंधान। निश्चित नेटवर्क और गैरऋणात्मक, जोड़ी जा सकने वाली लागतों के लिए। यह भौतिक दिशा या यात्रा की शर्तें स्वयं नहीं पहचानता।

नेटवर्क दर्ज करें

  • पहले Y? पर S+Ti दर्ज करें: S आरंभ और T गंतव्य है। फिर Y? पर अदिश किनारा a+bi और M? पर उसकी लागत बारी-बारी से दें। i के लिए ENG है। शीर्षों या किनारों की संख्या अलग से न दें।
  • समाप्ति के लिए अगले Y? पर केवल EXE, फिर M? पर केवल EXE दबाएँ। ये अलग प्रश्न हैं। ज्ञात शून्य लागत के लिए 0EXE दें।

पथ और लागत पढ़ें

  • हर Disp स्क्रीन S से शुरू होने वाला एक शीर्ष है। T सहित हर शीर्ष के बाद EXE दबाने पर अंत में कुल लागत आती है। −1 का अर्थ पथ नहीं। S=T पर S फिर 0 दिखता है। अंत में AC से निकलें; EXE फिर से चलाता है।

शर्तें और सीमाएँ

  • शीर्ष संख्या पूर्णांक 1–10, किनारे की लागत पूर्णांक 0–100 और अधिकतम 15 गैर-स्वलूप किनारे। समांतर किनारे अलग स्थान लेते हैं। लागत की इकाई समान रखें।
  • 15-किनारे वाला संस्करण शीर्ष सीमा और पूर्णांक लागत की पूरी जाँच नहीं करता। केवल समर्थित आँकड़े दें। ऋणात्मक या गायब लागत और क्षमता से अधिक प्रविष्टि पर Math ERROR है। क्षमता शेष हो तो खाली अंतिम-बिंदु के साथ गैरऋणात्मक लागत तथा स्वलूप अनदेखे होते हैं। भरने पर केवल दो खाली उत्तर से समाप्त करें।
  • साझा 680 bytes में से 547 bytes लगते हैं; दूसरे स्लॉट के लिए 133 bytes बचते हैं। हर बार A, B, C, D, X, Y, M और Ans मिटते हैं; जरूरी मान पहले सुरक्षित करें।
  • CMPLX, a+bi, Norm 1 में बनाएँ और चलाएँ। उदाहरण Deg और P1 में हैं। सामान्य समाप्ति Norm 1 लौटाती है। i दो पूर्णांक नाम जोड़ता है, काल्पनिक लागत नहीं है।
  • दिशायुक्त किनारे, ऋणात्मक भार और दस से अधिक शीर्ष समर्थित नहीं हैं। समान लागत के पथों में केवल एक मिलता है; सबसे कम किनारों की गारंटी नहीं। सीमित परिशुद्धता का अंतर कम है, इसलिए मूल कोड जस का तस रखें।

पूरा प्रोग्राम देखने के लिए साइन इन करें

पहुँच जाँची जा रही है…

प्रोग्राम कोड और परिशिष्ट एक साथ खुलते हैं।

पहुँच जाँची जा रही है…

पूरा प्रोग्राम देखने के लिए साइन इन करें

पहुँच जाँची जा रही है…

प्रोग्राम कोड और परिशिष्ट एक साथ खुलते हैं।