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