ডাইকস্ট্রা'স অ্যালগরিদম (Dijkstra's Algorithm)
ডাইকস্ট্রা'স অ্যালগরিদম একটি জনপ্রিয় গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা একটি সুত্র (source) ভেরটেক্স থেকে অন্য সব ভেরটেক্সের মধ্যে সর্বনিম্ন পাথ (shortest path) খুঁজে বের করতে ব্যবহৃত হয়। এটি মূলত ওজনযুক্ত গ্রাফে কাজ করে এবং ঋণাত্মক ওজনের এজ সমর্থন করে না।
অ্যালগরিদমের কাজ করার পদ্ধতি
- প্রাথমিক অবস্থান:
- একটি শুরু ভেরটেক্স নির্বাচন করুন। এর জন্য দূরত্ব 0 এবং অন্য সব ভেরটেক্সের জন্য অসীম (∞) নির্ধারণ করুন।
- প্রান্তিক ভেরটেক্স নির্বাচন:
- সমস্ত ভিজিট করা ভেরটেক্সের মধ্যে সবচেয়ে কম দূরত্ব সহ ভেরটেক্স নির্বাচন করুন (এটি প্রান্তিক ভেরটেক্স হবে)।
- দূরত্ব আপডেট:
- নির্বাচিত ভেরটেক্সের সমস্ত প্রতিবেশী ভেরটেক্সের জন্য পরীক্ষা করুন। যদি প্রতিবেশী ভেরটেক্সের নতুন দূরত্ব, বর্তমান দূরত্বের তুলনায় কম হয়, তবে এটি আপডেট করুন।
- রিপিট:
- পদ্ধতি চালিয়ে যান যতক্ষণ না সব ভেরটেক্স ভিজিট করা হয়।
- শেষ:
- সর্বনিম্ন দূরত্ব সহ সমস্ত ভেরটেক্সের জন্য দূরত্ব ফলস্বরূপ পাওয়া যাবে।
pseudocode for Dijkstra's Algorithm
উদাহরণ
ধরি, আমাদের একটি গ্রাফ আছে:
- ভেরটেক্স: A, B, C, D
- এজ: A-B (2), A-C (1), B-D (3), C-D (4)
ডাইকস্ট্রা অ্যালগরিদমের প্রক্রিয়া:
- শুরু করি A থেকে:
- dist[A] = 0, dist[B] = ∞, dist[C] = ∞, dist[D] = ∞
- A থেকে B (2) এবং C (1) এ যাত্রা করি:
- dist[B] = 2, dist[C] = 1
- এখন C এ যাব:
- A-C-D = 1 + 4 = 5 (dist[D] = 5, কিন্তু B-D এর মাধ্যমে (2 + 3 = 5) হবে, যা একই)
- শেষ পর্যন্ত B থেকে D এর মাধ্যমে:
- dist[B] = 2, dist[D] = 5
সুবিধা
- কার্যকারিতা: দ্রুত সর্বনিম্ন পথ খোঁজার জন্য কার্যকরী।
- সহজ বাস্তবায়ন: অ্যালগরিদমের গঠন সহজ এবং কাজ করা সহজ।
অসুবিধা
- ঋণাত্মক ওজনের সমস্যা: ডাইকস্ট্রা'স অ্যালগরিদম ঋণাত্মক ওজনের এজ নিয়ে কাজ করতে পারে না।
- স্থান ব্যবহার: বড় গ্রাফের জন্য অনেক মেমরি ব্যবহার করতে পারে।
সারসংক্ষেপ
ডাইকস্ট্রা'স অ্যালগরিদম একটি কার্যকরী অ্যালগরিদম, যা একটি গ্রাফের মধ্যে সর্বনিম্ন পাথ খোঁজার জন্য ব্যবহৃত হয়। এটি দ্রুত কাজ করে এবং গ্রাফের ভেরটেক্স এবং এজের মধ্যে সম্পর্ক বিশ্লেষণে সহায়ক।
Content added By
Read more
