মডিউল ৬_১ঃ কেন Dijkstra এলগরিদম আমাদের প্রয়োজন?

কেন Dijkstra এলগোরিদম প্রয়োজন সেটা বোঝার জন্য আগে এটা বুঝি যে কেন একটি weighted গ্রাফ এ BFS ঠিক উত্তর দেই না প্রায় সময়।

উপরের গ্রাফে যদি আমরা BFS এলগরিদম চালায় তাহলে শর্টেস্ট পাথ আসবে ০->১->৪। কিন্ত আমরা যদি ০ থেকে ৪ এ পোছানোর দুইটা রাস্তার মধ্যে কস্ট হিসেব করি তাহলে ০->১->৪ এই রাস্তায় কস্ট ১৫০ আর ০->২->৩->৪ এই রাস্তার কস্ট ২১। তাহলে বেস্ট পাথ হবে ০->২->৩->৪। এ সমস্যা সমাধান এর জন্য Dijkstra এলগরিদম প্রয়োজন।

আমরা Dijkstra এলগরিদম এর দুইটা এপ্রোচ শিখব।

১। নাইভ এপোচঃ এই এপ্রোচ এর কমপ্লেক্সিটি বেশি।

২। অপটিমাইজ এপ্রোজঃ নাইভ এপ্রোচকে অপটিমাইজ করে এই এপ্রোচ এ।