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