সংজ্ঞা
ডিজিক্সট্রা অ্যালগরিদম একটি নির্দিষ্ট নোড (সোর্স নোড) থেকে একটি সংযুক্ত গ্রাফের অন্যান্য সব নোডে শর্টেস্ট পাথ বের করে। এটি একটি শর্টেস্ট পাথ ট্রি তৈরি করে যার রুট হলো সোর্স নোড। এটি কম্পিউটার নেটওয়ার্কে রাউটিং কস্ট মিনিমাইজ করতে অপ্টিমাল রুট জেনারেট করতে ব্যাপকভাবে ব্যবহৃত হয়।
ডিজিক্সট্রা অ্যালগরিদম
ইনপুট - নেটওয়ার্ক প্রতিনিধিত্বকারী একটি গ্রাফ এবং একটি সোর্স নোড, s
আউটপুট - একটি শর্টেস্ট পাথ ট্রি, spt[], যার রুট নোড s।
ইনিশিয়ালাইজেশন
- dist[] অ্যারে (সাইজ |V|, নোড সংখ্যা), যেখানে dist[s] = 0 এবং dist[u] = ∞ (অনন্ত), u হলো s ছাড়া গ্রাফের যেকোনো নোড।
- Q অ্যারে, যেটিতে গ্রাফের সব নোড থাকে। অ্যালগরিদম শেষ হলে Q খালি হয়ে যাবে।
- S সেট, খালি। ভিজিটেড নোডগুলো এখানে যোগ হবে। শেষে S-তে গ্রাফের সব নোড থাকবে।
- while Q খালি নয়:
- Q-তে থেকে সবচেয়ে ছোট dist[u] دار নোড u বের করুন যা S-তে নেই। প্রথম রানে dist[s] বের হবে।
- u কে S-তে যোগ করুন (ভিজিটেড মার্ক করুন)।
- u-র সাথে অadyacent প্রতিটি নোড v-এর জন্য dist[v] আপডেট করুন:
- যদি (dist[u] + এজ u-v-এর ওজন) < dist[v] হয়, তবে dist[v] = dist[u] + এজ u-v-এর ওজন আপডেট করুন।
- অ্যারে dist[] এ s থেকে অন্যান্য সব নোডে শর্টেস্ট পাথ থাকবে।
উদাহরণ
অ্যালগরিদম বোঝার জন্য একটি উদাহরণ দেখি। নিচের গ্রাফে A থেকে G পর্যন্ত নোড রয়েছে, যেগুলো ওজনযুক্ত এজ দিয়ে সংযুক্ত।
ইনিশিয়ালাইজেশন:
- dist[7] = {0, ∞, ∞, ∞, ∞, ∞, ∞}
- Q = {A,B,C,D,E,F,G}
- S = ∅
Pass 1 - Q-তে থেকে A বের করা হয় (dist=0), S-তে যোগ করা হয়। A-র নোগবর B, C। dist[] আপডেট:
- dist[7] = {0, 5, 6, ∞, ∞, ∞, ∞}
- Q = {B,C,D,E,F,G}
- S = {A}
Pass 2 - B বের করা হয় (dist=5), S-তে যোগ। B-র নোগবর C, D, E। dist[] আপডেট:
- dist[7] = {0, 5, 6, 12, 13, ∞, ∞}
- Q = {C,D,E,F,G}
- S = {A,B}
Pass 3 - C বের করা হয় (dist=6), S-তে যোগ। C-র নোগবর D, F। dist[] আপডেট:
- dist[7] = {0, 5, 6, 8, 13, 10, ∞}
- Q = {D,E,F,G}
- S = {A,B,C}
Pass 4 - D বের করা হয় (dist=8), S-তে যোগ। D-র নোগবর E, F, G। dist[] আপডেট:
- dist[7] = {0, 5, 6, 8, 10, 10, 18}
- Q = {E,F,G}
- S = {A,B,C,D}
Pass 5 - E বা F যেকোনো একটা বের করা যায় (dist=10)। E বের করা হয়, S-তে যোগ। E-র নোগবর G। dist[] আপডেট:
- dist[7] = {0, 5, 6, 8, 10, 10, 13}
- Q = {F,G}
- S = {A,B,C,D,E}
Pass 6 - F বের করা হয় (dist=10), S-তে যোগ। F-র নোগবর G। G-এর dist কম থাকায় কোনো পরিবর্তন নেই।
- dist[7] = {0, 5, 6, 8, 10, 10, 13}
- Q = {G}
- S = {A,B,C,D,E,F}
Pass 7 - Q-তে শুধু G আছে। এটি বের করে S-তে যোগ করা হয়। dist[] পরিবর্তন নেই। Q খালি, S-তে সব নোড। অ্যালগরিদম শেষ। শর্টেস্ট পাথ ট্রি (সোর্স A থেকে সব নোড):
