Dijkstra's অ্যালগরিদম
Dijkstra's অ্যালগরিদম একটি গ্রাফে উৎস নোড থেকে অন্যান্য নোডে সর্বনিম্ন পথ (Shortest Path) খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি প্রাথমিকভাবে নন-নেগেটিভ ওয়েট সম্পন্ন গ্রাফের জন্য কার্যকর। এই অ্যালগরিদম গ্রাফের প্রতিটি নোডের সাথে উৎস নোডের দূরত্ব হিসাব করে এবং প্রতি ধাপে নিকটবর্তী নোডটি নির্বাচন করে চলতে থাকে।
Dijkstra's অ্যালগরিদমের ধাপসমূহ:
- প্রতিটি নোডের জন্য প্রাথমিকভাবে দূরত্ব অসীম হিসেবে সেট করুন, এবং উৎস নোডের জন্য দূরত্ব ০ হিসেবে নির্ধারণ করুন।
- একটি ভিজিটেড নোডের তালিকা তৈরি করুন এবং উৎস নোডটি যোগ করুন।
- উৎস নোড থেকে সরাসরি সংযুক্ত নোডগুলোর জন্য সর্বনিম্ন দূরত্ব আপডেট করুন।
- তারপর নিকটতম নোড নির্বাচন করুন এবং সেই নোড থেকে সংযুক্ত নোডগুলোর দূরত্ব আপডেট করুন।
- প্রতিটি নোড ভিজিট হওয়া পর্যন্ত উপরের প্রক্রিয়াটি পুনরাবৃত্তি করুন।
উদাহরণ:
ধরা যাক, একটি গ্রাফ আছে যেখানে নোড এবং প্রান্তের ওয়েট রয়েছে। Dijkstra's অ্যালগরিদম ব্যবহার করে উৎস নোড থেকে প্রতিটি নোডে সর্বনিম্ন পথ বের করা হয়।
Floyd-Warshall অ্যালগরিদম
Floyd-Warshall অ্যালগরিদম গ্রাফের প্রতিটি নোড থেকে অন্য প্রতিটি নোডে সর্বনিম্ন পথ নির্ণয় করার জন্য ব্যবহৃত হয়। এটি একটি ডায়নামিক প্রোগ্রামিং ভিত্তিক পদ্ধতি যা গ্রাফের সবকটি নোডের জন্য সংক্ষিপ্ততম পথ নির্ণয় করে। এই অ্যালগরিদমটি মূলত ন্যূনতম দূরত্বের ম্যাট্রিক্স আপডেট করে এবং ধাপে ধাপে সমাধান দেয়।
Floyd-Warshall অ্যালগরিদমের ধাপসমূহ:
- একটি দূরত্ব ম্যাট্রিক্স তৈরি করুন যেখানে প্রতিটি নোড থেকে অন্য নোড পর্যন্ত প্রাথমিক দূরত্ব দেয়া থাকবে।
- গ্রাফের প্রতিটি নোডকে একবার করে "মধ্যবর্তী নোড" হিসেবে বিবেচনা করুন।
- \( d[i][j] = \min(d[i][j], d[i][k] + d[k][j]) \) ব্যবহার করে প্রতিটি নোডের জন্য দূরত্ব আপডেট করুন।
- এই পদ্ধতিতে প্রতিটি নোডের মধ্য দিয়ে যাওয়ার পথে ন্যূনতম দূরত্ব খুঁজে পাওয়া যায়।
উদাহরণ:
ধরা যাক, একটি গ্রাফ আছে যেখানে \( A \), \( B \), এবং \( C \) নোড রয়েছে। এই তিনটি নোডের মধ্যে প্রতিটি পথে চলার সর্বনিম্ন দূরত্ব নির্ধারণ করতে Floyd-Warshall অ্যালগরিদম ব্যবহার করা হবে।
Dijkstra's অ্যালগরিদম একক উৎস থেকে নোডের সর্বনিম্ন পথ খুঁজতে ব্যবহার করা হয়, যেখানে Floyd-Warshall অ্যালগরিদম প্রতিটি নোড থেকে প্রতিটি নোডে সর্বনিম্ন পথ নির্ণয় করতে সক্ষম।
Read more
