কম্পিউটার নেটওয়ার্কে শর্টেস্ট পাথ অ্যালগরিদম (Shortest Path Algorithm)

কম্পিউটার নেটওয়ার্কে, শর্টেস্ট পাথ অ্যালগরिदমগুলো নেটওয়ার্ক নোডের মাঝপথে অপ্টিমাল পাথ খুঁজে বের করার লক্ষ্যে থাকে যাতে রাউটিং কস্ট মিনিমাইজ করা যায়। এগুলো গ্রাফ থিওরিতে প্রস্তাবিত শর্টেস্ট পাথ অ্যালগরिदমের ডাইরেক্ট অ্যাপ্লিকেশন।

ব্যাখ্যা

ধরুন একটি নেটওয়ার্ক N সংখ্যক ভার্টেক্স (নোড বা নেটওয়ার্ক ডিভাইস) দিয়ে গঠিত যা M সংখ্যক এজ (ট্রান্সমিশন লাইন) দিয়ে কানেক্টেড। প্রতিটি এজ একটি ওয়েইট के সাথে জড়িত থাকে, যা ফিজিক্যাল ডিস্ট্যান্স বা ট্রান্সমিশন লাইনের ট্রান্সমিশন ডিলে রিপ্রেজেন্ট করে। শর্টেস্ট পাথ অ্যালগরিদমের লক্ষ্য হলো যেকোনো দুটি ভার্টেক্সের মাঝপথে এজগুলো দিয়ে একটি রুট খুঁজে বের করা যাতে এজগুলোর ওয়েইটের সমষ্টি মিনিমাম হয়। যদি এজগুলোর ওয়েইট সমান হয়, তবে শর্টেস্ট পাথ অ্যালগরিদম ন্যূনতম হপ (hop) রুট খুঁজে বের করতে চায়।

সাধারণ শর্টেস্ট পাথ অ্যালগরিদম

কিছু সাধারণ শর্টেস্ট পাথ অ্যালগরিদম হলো:

• বেলমান ফোর্ড অ্যালগরিদম (Bellman Ford's Algorithm)
• ডাইজক্সট্রা অ্যালগরিদম (Dijkstra's Algorithm)
• ফ্লয়েড ওয়ার্শাল অ্যালগরিদম (Floyd Warshall's Algorithm)

নিচের সেকশনগুলো এই অ্যালগরিদমগুলো বর্ণনা করে।

বেলমান ফোর্ড অ্যালগরিদম (Bellman Ford Algorithm)

ইনপুট — নেটওয়ার্ক রিপ্রেজেন্ট করে একটি গ্রাফ; এবং একটি সোর্স নোড, s

আউটপুট — s থেকে অন্যান্য সকল নোড পর্যন্ত শর্টেস্ট পাথ।

• s থেকে সকল নোডের দূরত্ব অনন্ত (∞) হিসেবে ইনিশিয়ালাইজ করুন; নিজের দূরত্ব ০; একটি dist[] অ্যারে সাইজ |V| (নোডের সংখ্যা) দিয়ে যেখানে সব মান ∞ ছাড়া dist[s]।
• ইটারেটিভলি শর্টেস্ট ডিস্ট্যান্স ক্যালকুলেট করুন। |V|- 1 বার রিপিট করুন s ছাড়া প্রতিটি নোডের জন্য —
  • u এবং v ভার্টেক্স কানেক্ট করে এমন প্রতিটি এজের জন্য রিপিট করুন —
    • যদি dist[v] > (dist[u] + weight of edge u-v), তবে
      • dist[v] = dist[u] + weight of edge u-v আপডেট করুন
• dist[] অ্যারেতে s থেকে অন্যান্য সব নোড পর্যন্ত শর্টেস্ট পাথ থাকে।

ডাইজক্সট্রা অ্যালগরিদম (Dijkstra's Algorithm)

ইনপুট — নেটওয়ার্ক রিপ্রেজেন্ট করে একটি গ্রাফ; এবং একটি সোর্স নোড, s

আউটপুট — একটি শর্টেস্ট পাথ ট্রি, spt[], s কে রুট নোড হিসেবে।

ইনিশিয়ালাইজেশন (Initializations)

• ডিস্ট্যান্সের একটি অ্যারে dist[] সাইজ |V| (নোডের সংখ্যা), যেখানে dist[s] = 0 এবং dist[u] = ∞ (অনন্ত), u গ্রাফের একটি নোড s ছাড়া।
• একটি অ্যারে, Q, গ্রাফের সকল নোড ধারণ করে। অ্যালগরিদম কমপ্লিট হলে Q খালি হয়ে যাবে।
• একটি খালি সেট, S, যেখানে ভিজিটেড নোডগুলো অ্যাড হবে। অ্যালগরিদম কমপ্লিট হলে S গ্রাফের সকল নোড ধারণ করবে।
• Q খালি না হওয়া পর্যন্ত রিপিট করুন —
  • Q-তে থেকে স্মলেস্ট dist[u] 가진 নোড u রিমুভ করুন যা S-তে নেই। প্রথম রানে, dist[s] রিমুভ হবে।
  • u কে S-এ অ্যাড করুন, u কে ভিজিটেড মার্ক করুন।
  • u-এর সাথে এডজাসেন্ট প্রতিটি নোড v এর জন্য dist[v] আপডেট করুন যেন —
    • যদি (dist[u] + weight of edge u-v) < dist[v], তবে
      • dist[v] = dist[u] + weight of edge u-v আপডেট করুন
• dist[] অ্যারেতে s থেকে অন্যান্য সব নোড পর্যন্ত শর্টেস্ট পাথ থাকে।

ফ্লয়েড ওয়ার্শাল অ্যালগরিদম (Floyd Warshall Algorithm)

ইনপুট — একটি কস্ট এডজাসেন্সি ম্যাট্রিক্স, adj[][], নেটওয়ার্কে নোডগুলোর মাঝপথে পাথ রিপ্রেজেন্ট করে।

আউটপুট — একটি শর্টেস্ট পাথ কস্ট ম্যাট্রিক্স, cost[][], গ্রাফে প্রতিটি নোড পেয়ারের মাঝপথে কস্ট অনুযায়ী শর্টেস্ট পাথ দেখায়।

• cost[][] নিচের মতো পপুলেট করুন:
  • যদি adj[][] খালি হয় তবে cost[][] = ∞ (অনন্ত)
  • অন্যথায় cost[][] = adj[][]
• N = |V|, যেখানে V নেটওয়ার্কের নোড সেট রিপ্রেজেন্ট করে।
• k = 1 to N এর জন্য রিপিট করুন —
  • i = 1 to N এর জন্য রিপিট করুন —
    • j = 1 to N এর জন্য রিপিট করুন —
      • যদি cost[i][k] + cost[k][j] < cost[i][j], তবে
        • cost[i][j] := cost[i][k] + cost[k][j] আপডেট করুন
• ম্যাট্রিক্স cost[][] এ প্রতিটি নোড i থেকে অন্যান্য সকল নোড j পর্যন্ত শর্টেস্ট কস্ট থাকে।