\input header
{\rm Dijkstra's algorithm} (ডিয়েক্স্টরা) হল একটা {\rm weighted graph}-এর যে কোনো দুটো {\rm vertex}
a এবং b-এর মধ্যে একটা {\rm shorest path} বার করার {\rm algorithm}৷ এখানে একটা {\rm
path} -এর {\rm length} বলতে সেই {\rm path}-এর সব {\rm edge}-গুলোর {\rm weight}-এর যোগফল বোঝানো
হচ্ছে৷ {\rm Shortest path} মানে যে {\rm path}-এর {\rm
length} সবচেয়ে কম৷ এই সবচেয়ে কম {\rm
lenght}-টাকে বলে {\rm minimum distance between} a {\rm and} b৷
এই {\rm algorithm}-টার সঙ্গে {\rm Prim's algorithm}-এর বেশ মিল আছে৷ তবে এখানে ব্যাপারটা ঠিক
সাম্রাজ্য-বিস্তারের মত নয়৷বরং একটা ছোঁয়াচে রোগের সংক্রমণের
মত৷ {\rm Vertex} -গুলো যেনো কিছু লোক৷ তাদের কারুর শুরুতে কোনো রোগ নেই, একমাত্র a ছাড়া৷ a হচ্ছে
অনেকটা {\rm Prim's algorithm} এর {\rm home}-এর মতন৷ গোড়াতে কেবল a একাই অসুস্থ৷ ধাপে
ধাপে a-র থেকে রোগ ছড়াবে বাকীদের মধ্যে৷ প্রত্যেকটা {\rm vertex}-এর গায় একটা করে
সংখ্যা লেবেলের মত থাকবে৷ শুরুতে a-র লেবেল হবে ০ আর বাকীদের লেবেল \infty৷ এই
লেবেল্গুলো যেন স্বাস্থ্যের মান নির্দেশক---যত বড় সংখ্যা স্বাস্থ্য তত ভালো, ০ মানে
ভীষণ খারাপ অবস্থা, আর \infty মানে সম্পুর্ণ নীরোগ৷ যত রোগ ছড়াবে এই
সংখ্যাগুলো তত কমতে থাকবে৷
\end{document}
\input header
রোগটা ছড়াবে এইভাবে---
প্রত্যেকটা ধাপে কেবলমাত্র একটা করে {\rm vertex}-ই রোগ ছড়াবে তার প্রতিবেশীদের
মধ্যে৷
যে {\rm vertex} একবার রোগ ছড়িয়েছে সে ভবিষ্যতে আর কখনো রোগ ছড়াতে পারবে না৷
যারা এখনো রোগ ছড়ায় নি, তাদেরকে আমরা বলব {\rm available vertices.}
কোনো {\rm step}-এ {\rm available vertices}-এর মধ্যে যার লেবেল সবচেয়ে কম, (অর্থাৎ যে
সর্বাধিক রোগগ্রস্ত), সেই {\rm step}-এ সেই {\rm vertex}-টা ই কেবল রোগ ছড়াবে৷ সর্বাধিক
রোগগ্রস্ত একাধিক {\rm vertex} থাকলে, তাদের থেকে যে কোনো একজন রোগ ছড়াবে৷ অর্থাৎ, {\rm ties are broken arbitrarily}৷
ধর u বলে একটা {\rm vertex} রোগ ছড়াচ্ছে৷ তার মানে uতার সব প্রতিবেশী {\rm
vertex}-গুলো লেবেল কমাবার চেষ্টা করবে৷ মনে কর v একটা প্রতিবেশী৷ u-এর লেবেল
\lambda(u), v-এর লেবেল \lambda(v), আর \{u,v\} {\rm edge}-টার {\rm weight} w৷
এই w-টা যেন u আর v-এর মধ্যে দূরত্ব৷ w যত কম হবে, u তত
বেশী করে v-কে সংক্রামিত করতে পারবে৷ uচেষ্টা করবে v-এর লেবেলটাকে
কমিয়ে \lambda(u) +w করতে৷ যদি \lambda(v) আগে থেকেই এর থেকে কম থাকে তবে
u এর সংক্রমণের চেষ্টা ব্যর্থ হবে৷
\end{document}
\input header
তা না হলে \lambda(v) কমে হবে \lambda(u) +w অর্থাৎ u তার রোগ দিয়ে v-এর
স্বাস্থ্যহানি করতে সফল হয়েছে৷ এই ক্ষেত্রে আমরা \{u,v\} {\rm edge}-এর পাশে একটা
ছোট্টো তীর চিহ্ন এঁকে দেব uথেকে v-এর দিকে৷ অর্থাৎ v-এর সর্বনাশের কারণ
হল u৷
এইভাবে প্রত্যেকধাপে সবচেয়ে রুগ্ন একটা {\rm available vertex} তার প্রতিবেশীদের মধ্যে রোগ
ছড়াবে৷ এইভাবে চলতে চলতে একসময়ে b {\rm vertex}-টা\end{document}
\input header
যখন {\rm available vertex}-দের মধ্যে সবচেয়ে রুগ্ন হবে (অর্থাৎ লেবেলটা সবচেয়ে ছোটো হবে),
তখন {\rm algorithm}-টা থামবে৷ b-এর লেবেলটা সেই সময়ে হবে {\rm minimum distance between} a অন্দ b.
আর তীর চিহ্নগুলো ধরে ধরে a থেকে b পর্যন্ত একটা {\rm shortest path} পাওয়া যাবে৷
-------------------
{\rm Algorithm}-টা খুব একটা সহজ নয়, এবং এর জন্য কোনো {\rm standard notation}-ও নেই৷ তাই ছবি এঁকে
বিভিন্ন {\rm step}-গুলো বোঝানোর আগে আমাদের একটা {\rm notation} ঠিক করে নেওয়া দরকার৷ প্রত্যেক {\rm step}-এর
ছবিতে আমরা কেবল রুগ্ন {\rm vertex}-গুলোই আঁকব, অর্থাৎ যে সব {\rm vertex}-এর লেবেল \infty নয়৷
যে {\rm vertex}-টা রোগ ছড়াচ্ছে তার পাশে একটা টিক্ চিহ্ন এঁকে দেব৷ আর সবগুলো {\rm edge} আঁকার
কোনো দরকার নেই৷ কেবল যে যে {\rm edge} বরাবর রোগ ছড়িছে সেগুলো দেখালেই হবে৷ এই নিয়মগুলোর
উদ্দেশ্য একটাই, যাতে যথাসম্ভব কম এঁকে যাবতীয় তথ্য প্রকাশ করা যায়৷ আগেই বলেছি যে
এই {\rm notation}-টা {\rm standard} কিছু নয়৷ অতএব অন্য কাউকে বোঝানোর সময়ে গোড়তেই {\rm notation}-টা
লিখে নেওয়া দরকার৷ সেই সময়ে যেন রোগ, সংক্রমণ, স্বাস্থ্য এই সব ভাষা ব্যবহার কোরো না,
ওগুলো কেবল নিজের বোঝার সুবিধের জন্য৷\end{document}