ডিজকস্ট্রার সংক্ষিপ্ততম পাথ অ্যালগরিদমের জন্য সি++ প্রোগ্রাম?

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

Dijkstra-এর অ্যালগরিদম উৎস থেকে ন্যূনতম দূরত্ব আছে এমন নোডের একটি সেট তৈরি করে একটি একক উৎস নোড থেকে একটি সংক্ষিপ্ত পথের গাছ খুঁজে পায়।

গ্রাফটিতে নিম্নলিখিতগুলি রয়েছে−

• শীর্ষবিন্দু, বা নোড, অ্যালগরিদমে v বা u দ্বারা চিহ্নিত।

• ওজনযুক্ত প্রান্তগুলি যা দুটি নোডকে সংযুক্ত করে:(u,v) একটি প্রান্ত নির্দেশ করে এবং w(u,v) এর ওজন বোঝায়। ডানদিকের চিত্রে, প্রতিটি প্রান্তের ওজন ধূসর রঙে লেখা আছে।

অ্যালগরিদম ধাপ

• উৎস শীর্ষবিন্দু ব্যতীত সমস্ত শীর্ষের দূরত্ব =অসীমতা সেট করুন, উৎস দূরত্ব =0 সেট করুন।
• উৎস শীর্ষবিন্দুকে একটি ন্যূনতম-অগ্রাধিকার সারিতে ঠেলে দিন ফর্মে (দূরত্ব, শীর্ষবিন্দু), কারণ ন্যূনতম অগ্রাধিকার সারিতে তুলনা হবে শীর্ষবিন্দুর দূরত্ব অনুযায়ী৷
• অগ্রাধিকার সারি থেকে ন্যূনতম দূরত্ব সহ শীর্ষবিন্দুটি পপ করুন (প্রথমে পপড শীর্ষ =উৎস)।
• "বর্তমান শীর্ষবিন্দু দূরত্ব + প্রান্তের ওজন <পরবর্তী শীর্ষবিন্দু দূরত্ব" এর ক্ষেত্রে পপড শীর্ষবিন্দুতে সংযুক্ত শীর্ষবিন্দুগুলির দূরত্ব আপডেট করুন, তারপর অগ্রাধিকার সারিতে নতুন দূরত্ব সহ শীর্ষবিন্দুটিকে ঠেলে দিন৷
• যদি পপড শীর্ষবিন্দুটি আগে পরিদর্শন করা হয় তবে এটি ব্যবহার না করেই চালিয়ে যান।
• অগ্রাধিকার সারি খালি না হওয়া পর্যন্ত একই অ্যালগরিদম আবার প্রয়োগ করুন৷

গ্রাফে একটি গ্রাফ এবং একটি উত্স শীর্ষবিন্দু দেওয়া হয়েছে, প্রদত্ত গ্রাফে উত্স থেকে সমস্ত শীর্ষবিন্দু পর্যন্ত সংক্ষিপ্ততম পথগুলি সন্ধান করুন। গ্রাফের ওজনের G[][] ম্যাট্রিক্স দেওয়া হয়েছে, গ্রাফে শীর্ষবিন্দুর n নম্বর, u প্রারম্ভিক নোড।

ইনপুট

G[max][max]={{0,1,0,3,10}, {1,0,5,0,0}, {0,5,0,2,1}, {3 ,0,2,0,6}, {10,0,1,6,0}}n=5u=0

আউটপুট

নোড1=1পথ=1<-0নোডের দূরত্ব2=5পাথ=2<-3<-0নোডের দূরত্ব3=3পথ=3<-0নোডের দূরত্ব=6পথ=4<-2<-3<-0 

 ব্যাখ্যা 
 
 
 

 সংলগ্ন ম্যাট্রিক্স অ্যাডজ[ ][ ] থেকে খরচ ম্যাট্রিক্স C[ ][ ] তৈরি করুন। C[i][j] হল vertex i থেকে vertex j-এ যাওয়ার খরচ। যদি শীর্ষবিন্দু i এবং j এর মধ্যে কোন প্রান্ত না থাকে তাহলে C[i][j] হল অসীম।
 
 
 

 পরিদর্শন করা অ্যারেটি শূন্য থেকে শুরু করা হয়েছে।
 
 
 
এর জন্য(i=0;i 
 
 

 যদি শীর্ষবিন্দু 0 উৎস শীর্ষবিন্দু হয় তাহলে পরিদর্শন করা[0]কে 1 হিসেবে চিহ্নিত করা হয়।
 
 
 

 শীর্ষবিন্দু নং থেকে শীর্ষবিন্দুর খরচ সংরক্ষণ করে দূরত্ব ম্যাট্রিক্স তৈরি করুন। উৎস শীর্ষবিন্দু থেকে 0 থেকে n-1 পর্যন্ত 0।
 
 
 
(i=1;i 

 প্রাথমিকভাবে, উৎস শীর্ষবিন্দুর দূরত্ব 0 হিসাবে নেওয়া হয়। অর্থাৎ দূরত্ব[0]=0;
 
এর জন্য(i=1;i 
 
 

 একটি শীর্ষবিন্দু চয়ন করুন, যেমন দূরত্ব[w] সর্বনিম্ন এবং পরিদর্শন[w] 0 হয়। পরিদর্শন করা[w] 1 হিসাবে চিহ্নিত করুন।
 
 
 

 উৎস থেকে অবশিষ্ট শীর্ষবিন্দুগুলির সর্বনিম্ন দূরত্ব পুনরায় গণনা করুন।
 
 
 

 কেবলমাত্র, পরিদর্শন করা অ্যারেতে 1 হিসাবে চিহ্নিত নয় এমন শীর্ষবিন্দুগুলিকে দূরত্বের পুনঃগণনার জন্য বিবেচনা করা উচিত। অর্থাৎ প্রতিটি শীর্ষবিন্দু v
 এর জন্য 
 
 <প্রে>যদি(ভিজিট করা[v]==0) দূরত্ব[v]=মিনিট(দূরত্ব[v], দূরত্ব[w]+ খরচ[w][v])
 
উদাহরণ
 
#include#includeNamespace std ব্যবহার করে;#define INFINITY 9999#define max 5void dijkstra(int G[max][max],int n,int startnode);int main() { int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0 ,2,0,6},{10,0,1,6,0}}; int n=5; int u =0; dijkstra(G,n,u); রিটার্ন 0;} void dijkstra(int G[max][max],int n,int startnode) { int cost[max][max],দূরত্ব[max],pred[max]; পরিদর্শন করা int (i=0;i