113গণিত · বিশ্ববিদ্যালয় গণিত · গ্রাফ তত্ত্ব

ক্ষুদ্রতম পথ: 20টি প্রান্ত

fx-50FH II · CMPLX · 637 bytes

সর্বোচ্চ দশটি শীর্ষ ও 20টি প্রান্তের অনির্দেশিত নেটওয়ার্কে ন্যূনতম খরচের একটি পথ বের করুন; শীর্ষগুলি ক্রমে, শেষে মোট খরচ দেখায়।

  • ৬৩৭ বাইট
  • CMPLX মোড
01

সমাধানসহ উদাহরণ

উদাহরণ ১

বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: জাদুঘরের রোবট নম্বরযুক্ত কক্ষে চলাচল করে। সংযোগ দ্বিমুখী, খরচ মিনিটে। 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
ক্যালকুলেটরে করুন

উদাহরণ ২

বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: প্রদর্শনীর শাটল নেটওয়ার্কে পূর্ণসংখ্যায় ভাড়া। 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
ক্যালকুলেটরে করুন

উদাহরণ ৩

বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: প্রশিক্ষণ যোগাযোগ নেটওয়ার্ক দশটি ভার্চুয়াল টার্মিনাল যুক্ত করে। প্রতিটি দ্বিমুখী সংযোগের স্থির পূর্ণসংখ্যা প্রেরণ খরচ আছে। শেষের সংযোগসহ সব 20টি তালিকার ক্রমে দিয়ে 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–4: 1; 4–7: 1; 7–10: 1; 1–8: 9; 3–10: 8

উত্তর
1 → 4 → 7 → 10; মোট খরচ 1+1+1=3
মানক সমাধান (ক্যালকুলেটর ছাড়া)
  1. S থেকে Dijkstra চালান। u সদ্য নির্ধারিত শীর্ষ, d(v) হালনাগাদ অস্থায়ী দূরত্ব, ∞ এখনও অপ্রাপ্য।
  2. u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
  3. u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
  4. u=7, d(7)=2; d(8)=4, d(10)=3
  5. u=10, d(10)=3; d(9)=7
  6. পূর্বসূরি থেকে পথ ফিরে সরাসরি খরচ যোগ করুন: 1 → 4 → 7 → 10; মোট খরচ 1+1+1=3
ক্যালকুলেটরে করুন
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; সর্বোচ্চ 20টি স্ব-লুপবিহীন প্রান্ত। সমান্তরাল প্রান্ত প্রতিটি একটি স্থান নেয়। সব খরচের একক একই রাখুন।
  • 20-প্রান্ত সংস্করণ প্রান্তবিন্দু ও খরচের পূর্ণসংখ্যা এবং সীমা যাচাই করে। একটি ঘর ফাঁকা, অবৈধ মান বা অতিরিক্ত প্রান্তে Math ERROR। জায়গা থাকলে বৈধ স্ব-লুপ উপেক্ষিত; পূর্ণ হলে শুধু দুই ফাঁকা উত্তরে শেষ হয়।
  • যৌথ 680 bytes-এর 637 bytes ব্যবহৃত হয়, অন্য স্লটে 43 bytes থাকে। প্রতি চালনায় A, B, C, D, X, Y, M ও Ans মুছে যায়; দরকারি মান আগে রাখুন।
  • CMPLX, a+bi, Norm 1-এ তৈরি ও চালান। উদাহরণে Deg ও P1। স্বাভাবিক সমাপ্তিতে Norm 1 ফেরে। i দুটি পূর্ণসংখ্যা নম্বর মেলায়, কাল্পনিক খরচ নয়।
  • নির্দেশিত প্রান্ত, ঋণাত্মক ওজন ও দশের বেশি শীর্ষ সমর্থিত নয়। সমান খরচে একটি পথই দেয়; সর্বনিম্ন প্রান্তসংখ্যার নিশ্চয়তা নেই। সীমিত নির্ভুলতার ব্যবধান কম, তাই কোড হুবহু রাখুন।

সম্পূর্ণ প্রোগ্রাম খুলতে সাইন ইন করুন

প্রবেশাধিকার যাচাই হচ্ছে…

প্রোগ্রাম কোড ও পরিশিষ্ট একসঙ্গে খুলবে।

প্রবেশাধিকার যাচাই হচ্ছে…

সম্পূর্ণ প্রোগ্রাম খুলতে সাইন ইন করুন

প্রবেশাধিকার যাচাই হচ্ছে…

প্রোগ্রাম কোড ও পরিশিষ্ট একসঙ্গে খুলবে।