Dijkstra’s Algorithm হলো একটি সুপরিচিত গ্রাফ অ্যালগরিদম, যা একটি উৎস (source) শীর্ষবিন্দু থেকে অন্যান্য সকল শীর্ষবিন্দু পর্যন্ত সর্বনিম্ন পথ (shortest path) নির্ধারণ করতে ব্যবহৃত হয়। এটি positive বা non-negative edge weight বিশিষ্ট গ্রাফের জন্য উপযুক্ত।
মূল তথ্যসমূহ:
-
কার্যপদ্ধতি: Dijkstra’s অ্যালগরিদম একটি greedy approach অনুসরণ করে, যেখানে প্রতি ধাপে সবচেয়ে ছোট দূরত্বযুক্ত নোড নির্বাচন করা হয় এবং তার প্রতিবেশী নোডগুলোর দূরত্ব আপডেট করা হয়।
-
শর্ত: এটি কেবল তখনই সঠিকভাবে কাজ করে যখন সব edge weight শূন্য বা ধনাত্মক (≥ 0) হয়।
-
ডেটা স্ট্রাকচার: সাধারণত এটি priority queue (min-heap) ব্যবহার করে দ্রুততম নোড নির্বাচন করতে।
-
সময়সীমা (Time Complexity):
-
O(V²) — সরল বাস্তবায়নের ক্ষেত্রে।
-
O((V + E) log V) — যদি priority queue ব্যবহার করা হয়।
-
ভুল বিকল্পসমূহ:
-
ক) Prim’s Algorithm: এটি Minimum Spanning Tree (MST) তৈরি করে, shortest path নয়।
-
খ) Kruskal’s Algorithm: এটিও MST নির্মাণে ব্যবহৃত হয়, shortest path নির্ধারণে নয়।
-
ঘ) DFS (Depth First Search): এটি কেবল গ্রাফ ট্রাভার্সাল-এর জন্য ব্যবহৃত হয়, shortest path নির্ধারণের জন্য নয়।
অতএব, Dijkstra’s Algorithm-ই সঠিক উত্তর, কারণ এটি positive weighted graph-এর shortest path নির্ণয়ে ব্যবহৃত হয়।
