কম্পিউটার নেটওয়ার্কে সংক্ষিপ্ততম পাথ অ্যালগরিদম

কম্পিউটার নেটওয়ার্কে, সংক্ষিপ্ততম পাথ অ্যালগরিদমের লক্ষ্য থাকে নেটওয়ার্ক নোডের মধ্যে সর্বোত্তম পথ খুঁজে বের করা যাতে রাউটিং খরচ কম হয়। এগুলি গ্রাফ তত্ত্বে প্রস্তাবিত সংক্ষিপ্ততম পাথ অ্যালগরিদমের সরাসরি প্রয়োগ৷

ব্যাখ্যা

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

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

কিছু সাধারণ সংক্ষিপ্ত পথ অ্যালগরিদম হল −

• বেলম্যান ফোর্ডের অ্যালগরিদম

• ডিজকস্ট্রার অ্যালগরিদম

• ফ্লয়েড ওয়ারশালের অ্যালগরিদম

নিম্নলিখিত বিভাগগুলি এই অ্যালগরিদমগুলির প্রত্যেকটি বর্ণনা করে৷

বেলম্যান ফোর্ড অ্যালগরিদম

ইনপুট - নেটওয়ার্কের প্রতিনিধিত্বকারী একটি গ্রাফ; এবং একটি উৎস নোড, s

আউটপুট − s থেকে অন্য সব নোডের সবচেয়ে ছোট পথ।

• s থেকে সমস্ত নোডের দূরত্বকে অসীম হিসাবে শুরু করুন (∞); 0 হিসাবে নিজের থেকে দূরত্ব; একটি অ্যারে dist[] আকার |V| (নোডের সংখ্যা) dist[s] ছাড়া ∞ হিসাবে সমস্ত মান সহ .

• পুনরাবৃত্তিমূলকভাবে সংক্ষিপ্ততম দূরত্ব গণনা করুন। পুনরাবৃত্তি করুন |V|- 1 s −

  ছাড়া প্রতিটি নোডের জন্য বার

  • প্রতিটি প্রান্ত সংযোগকারী শীর্ষবিন্দু u এবং v −

    এর জন্য পুনরাবৃত্তি করুন

    • যদি dist[v]> (dist[u] + প্রান্তের ওজন u-v) , তারপর

      • আপডেট করুন dist[v] =dist[u] + প্রান্তের ওজন u-v

• অ্যারে dist[] s থেকে অন্য প্রতিটি নোডের সংক্ষিপ্ততম পথ রয়েছে।

ডিজকস্ট্রার অ্যালগরিদম

ইনপুট - নেটওয়ার্কের প্রতিনিধিত্বকারী একটি গ্রাফ; এবং একটি উৎস নোড, s

আউটপুট − একটি সংক্ষিপ্ত পথ গাছ, spt[], রুট নোড হিসাবে s সহ।

সূচনা -

• দূরত্বের একটি বিন্যাস dist[] আকার |V| (নোডের সংখ্যা), যেখানে dist[s] =0 এবং dist[u] =∞ (অসীম), যেখানে u গ্রাফে s ছাড়া একটি নোড উপস্থাপন করে।

• একটি অ্যারে, Q , গ্রাফে সমস্ত নোড রয়েছে। যখন অ্যালগরিদম সম্পূর্ণ হয়, Q খালি হয়ে যাবে।

• একটি খালি সেট, S , যেখানে পরিদর্শন করা নোড যোগ করা হবে। যখন অ্যালগরিদম সম্পূর্ণ হয়, S গ্রাফের সমস্ত নোড থাকবে৷

  ৷

• Q সময় পুনরাবৃত্তি করুন খালি নয় -

  • Q থেকে সরান , নোড, u সবচেয়ে ছোট dist[u] থাকা এবং যা S-এ নেই . প্রথম দৌড়ে, dist[s] সরানো হয়।

  • u যোগ করুন S থেকে , আপনাকে পরিদর্শন করা হিসাবে চিহ্নিত করছে৷

    ৷

  • প্রতিটি নোডের জন্য v যা u এর সংলগ্ন , dist[v] আপডেট করুন যেমন −

    • যদি (dist[u] + প্রান্তের ওজন u-v) dist[v] , তারপর

      • আপডেট করুন dist[v] =dist[u] + প্রান্তের ওজন u-v

• অ্যারে dist[] s থেকে সংক্ষিপ্ততম পথ রয়েছে প্রতিটি অন্য নোডে।

ফ্লয়েড ওয়ারশাল অ্যালগরিদম

ইনপুট − একটি খরচ সংলগ্ন ম্যাট্রিক্স, adj[][][] , নেটওয়ার্কের মধ্যে নোডের মধ্যে পাথ প্রতিনিধিত্ব করে।

আউটপুট − একটি সংক্ষিপ্ত পথ খরচ ম্যাট্রিক্স, কস্ট[][] , গ্রাফে প্রতিটি জোড়া নোডের মধ্যে খরচের পরিপ্রেক্ষিতে সংক্ষিপ্ততম পথ দেখায়৷

• খরচ[][] পপুলেট করুন নিম্নরূপ:

  • যদি adj[][] খালি তারপর কস্ট[][] =∞ (অসীম)

  • অন্যথায় খরচ[][] =adj[][]

• N =|V| , যেখানে V নেটওয়ার্কে নোডের সেট প্রতিনিধিত্ব করে।

• k =1 থেকে N এর জন্য পুনরাবৃত্তি করুন −

  • i =1 থেকে N এর জন্য পুনরাবৃত্তি করুন −

    • j =1 থেকে N এর জন্য পুনরাবৃত্তি করুন −

      • যদি খরচ[i][k] + খরচ[k][j] খরচ[i][j] , তারপর

        • খরচ[i][j] আপডেট করুন :=খরচ[i][k] + খরচ[k][j]

• ম্যাট্রিক্স কস্ট[][] প্রতিটি নোড থেকে সংক্ষিপ্ততম খরচ রয়েছে, i , প্রতিটি অন্য নোডে, j .