গ্রাফের ছোট পথ খোঁজার জন্য দুটি প্রধান অ্যালগরিদম হল Dijkstra’s Algorithm এবং Bellman-Ford Algorithm। উভয় অ্যালগরিদমই গ্রাফের মধ্যে এক বা একাধিক উত্স থেকে গন্তব্য পর্যন্ত সবচেয়ে সংক্ষিপ্ত পথ খুঁজে বের করতে ব্যবহৃত হয়, তবে তাদের কাজ করার পদ্ধতি এবং সীমাবদ্ধতা ভিন্ন।
Dijkstra’s Algorithm
বর্ণনা: Dijkstra’s Algorithm হল একটি গ্রাফ অ্যালগরিদম যা কোনও একটি উত্স নোড থেকে অন্যান্য সমস্ত নোডের জন্য সর্বনিম্ন ওজনের পথ খুঁজে বের করে। এটি ইতিবাচক ওজনের গ্রাফে কার্যকরী।
কিভাবে কাজ করে:
- প্রাথমিককরণ: উত্স নোডের দূরত্ব 0 হিসাবে সেট করুন এবং অন্যান্য সমস্ত নোডের জন্য অর্ন্তগত দূরত্ব অসীম (Infinity) হিসাবে সেট করুন।
- নোড নির্বাচন: একটি অপ্রস্তুত নোড তালিকা থেকে সর্বনিম্ন দূরত্বের নোড নির্বাচন করুন এবং সেটিকে প্রক্রিয়াকৃত নোড হিসাবে চিহ্নিত করুন।
- দূরত্ব আপডেট: নির্বাচিত নোডের সংযুক্ত নোডগুলির জন্য দূরত্ব আপডেট করুন। যদি নতুন দূরত্ব পুরানো দূরত্বের চেয়ে কম হয় তবে সেটিকে আপডেট করুন।
- পুনরাবৃত্তি: প্রতিটি নোডের জন্য এই প্রক্রিয়া পুনরাবৃত্তি করুন যতক্ষণ না সমস্ত নোড প্রক্রিয়াকৃত হয়।
টাইম কমপ্লেক্সিটি:
- \( O(V^2) \) (যেখানে \( V \) হল নোডের সংখ্যা) যদি সোজা অ্যারের মাধ্যমে বাস্তবায়িত হয়।
- \( O(E + V \log V) \) (যেখানে \( E \) হল এজের সংখ্যা) যদি প্রাধান্য কিউ (Priority Queue) ব্যবহার করা হয়।
Bellman-Ford Algorithm
বর্ণনা: Bellman-Ford Algorithm হল একটি গ্রাফ অ্যালগরিদম যা কোনও একটি উত্স নোড থেকে অন্যান্য নোডের জন্য সর্বনিম্ন দূরত্ব নির্ধারণ করতে ব্যবহৃত হয়। এটি নেতিবাচক ওজনের এজগুলি সহ গ্রাফে কাজ করতে সক্ষম।
কিভাবে কাজ করে:
- প্রাথমিককরণ: উত্স নোডের দূরত্ব 0 হিসাবে এবং অন্যান্য নোডের জন্য অসীম (Infinity) হিসাবে সেট করুন।
- এজ আপডেট:\( V-1 \) বার সকল এজগুলির জন্য নিম্নলিখিত কাজ করুন:
- প্রতিটি এজ \( (u, v) \) এর জন্য চেক করুন: যদি \( distance[u] + weight < distance[v] \) হয়, তবে \( distance[v] \) আপডেট করুন। - নেতিবাচক চক্র পরীক্ষা: সমস্ত এজগুলির জন্য পুনরাবৃত্তি করুন। যদি কোনও দূরত্ব আপডেট হয়, তবে গ্রাফে নেতিবাচক চক্র রয়েছে।
টাইম কমপ্লেক্সিটি:
- \( O(V \times E) \) (যেখানে \( V \) হল নোডের সংখ্যা এবং \( E \) হল এজের সংখ্যা)।
তুলনা
| অ্যালগরিদম | Dijkstra’s Algorithm | Bellman-Ford Algorithm |
|---|---|---|
| ওজনের সীমা | শুধুমাত্র ইতিবাচক ওজন | নেতিবাচক ওজন সমর্থন করে |
| টাইম কমপ্লেক্সিটি | \( O(V^2) \) বা \( O(E + V \log V) \) | \( O(V \times E) \) |
| গাণিতিক গঠন | গ্রাফের ওজন কমিয়ে আসে | নেতিবাচক চক্র পরীক্ষা করে |
| নির্ধারণ পদ্ধতি | প্রাধান্য কিউ ব্যবহার করে | ইটারেটিভ আপডেট ব্যবহার করে |
উপসংহার
Dijkstra’s Algorithm এবং Bellman-Ford Algorithm উভয়ই গ্রাফে ছোট পথ খুঁজে বের করার জন্য গুরুত্বপূর্ণ অ্যালগরিদম। Dijkstra’s Algorithm দ্রুত এবং দক্ষ, কিন্তু এটি নেতিবাচক ওজনের এজের জন্য কাজ করে না। অন্যদিকে, Bellman-Ford Algorithm নেতিবাচক ওজনের জন্য সমর্থন প্রদান করে, তবে এটি ধীরগতির। সমস্যা অনুযায়ী সঠিক অ্যালগরিদম নির্বাচন করা জরুরি।
