আমরা শুরুতেই শিখেছি কিভাবে শর্টেস্ট পাথে এক জায়গা থেকে আরেক জায়গায় যেতে হয়। সেজন্য আমরা শিখেছি ব্রেডথ ফার্স্ট সার্চ নামের একটি সার্চিং অ্যালগোরিদম। অ্যালগোরিদমটি চমৎকার কিন্তু সমস্যা হলো সে ধরে নেয় প্রতিটি রাস্তা দিয়ে যেতে সমান সময় লাগে, মানে সব এজ এর কস্ট সমান। প্র্যাকটিকাল লাইফে বেশিভাগ ক্ষেত্রেই এটা অচল হয়ে পড়ে, তখন আমাদের দরকার পরে ডায়াক্সট্রা। প্রথমে নাম শুনে আমার ধারণা হয়েছিলো ডায়াক্সট্রা খুবই ভয়ংকর কোনো জিনিস কিন্তু আসলে বিএফএস লেখার মতোই সহজ ডায়াক্সট্রা লেখা, আমি তোমাদের দেখানোর চেষ্টা করবো কিভাবে বিএফএসকে কিছুটা পরিবর্তন করে একটা প্রায়োরিটি কিউ যোগ করে সেটাকে ডায়াক্সট্রা বানিয়ে ফেলা যায়।
ডায়াক্সট্রা শুরু করার আগে আমরা পাথ রিল্যাক্সেশন(relax) নামের একটা ছোট্ট জিনিসের সাথে পরিচিত হই। ধরো সোর্স থেকে প্রতিটা নোডের ডিসটেন্স রাখা হয়েছে $d[]$ অ্যারেতে। যেমন $d[3]$ মানে হলো সোর্স থেকে বিভিন্ন এজ পার হয়ে ৩ এ আসতে মোট $d[3]$ ডিসটেন্স লেগেছে। যদি ডিসটেন্স জানা না থাকে তাহলে ইনফিনিটি অর্থাৎ অনেক বড় একটা মান রেখে দিবো। আর $cost[u][v]$ তে রাখা আছে $u – v$ এজ এর cost।
ধরো তুমি বিভিন্ন জায়গা ঘুরে ফার্মগেট থেকে টিএসসি তে গেলে ১০ মিনিটে, আবার ফার্মগেট থেকে কার্জন হলে গেলে ২৫ মিনিটে। তাহলে তোমার কাছে ইনফরমেশন আছে:
d[টিএসসি] = ১০, d[কার্জনহল] = ২৫
এখন তুমি দেখলে টিএসসি থেকে ৭ মিনিটে কার্জনে চলে যাওয়া যায়,
cost[টিএসসি][কার্জন] = ৭
তাহলে তুমি ২৫ মিনিটের জায়গায় মাত্র ১০ + ৭ = ১৭ মিনিটে কার্জনহলে যেতে পারবে। যেহেতু তুমি দেখেছো:
d[টিএসসি] + cost[টিএসসি][কার্জন] < d[কার্জনহল]
তাই তুমি এই নতুন রাস্তা দিয়ে কার্জন হলে গিয়ে d[কার্জনহল] = d[টিএসসি] + cost[টিএসসি][কার্জন] বানিয়ে দিতেই পারো!!
উপরের ছবিটা সেটাই বলছে। আমরা u থেকে v তে যাবো যদি d[u] + cost[u][v] < d[v] হয়। আর $d[v]$ কে আপডেট করে $d[v] = d[u] + cost[u][v]$ বানিয়ে দিবো। ভবিষ্যতে যদি কার্জনহলে অন্য রাস্তা দিয়ে আরো কম সময়ে যেতে পারি তখন সেই রাস্তা এভাবে কম্পেয়ার করে আপডেট করি দিবো। ব্যাপারটা অনেকটা এরকম:
|
1 2 |
if d[u] + cost[u][v] < d[v]: d[v] = d[u] + cost[u][v] |
উপরের অংশটা যদি বুঝে থাকো তাহলে ডায়াক্সট্রা বোঝার ৬০% কাজ হয়ে গেছে। না বুঝে থাকলে আবার পড়ো।
বিএফএস নিশ্চয়ই তুমি ভালো করে বুঝো। বিএফএস এ আমাদের একটা নোডে কখনো দুইবার যাওয়া দরকার হয়নি, আমরা প্রতিবার দেখেছি একটা নোড ভিজিটেড কিনা, যদি ভিজিটেড না হয় তাহলে সেই নোডকে কিউতে পুশ করে দিয়েছি এবং ডিসটেন্স ১ বাড়িয়ে দিয়েছি। ডায়াক্সট্রাতে আমরা একই ভাবে কিউ তে নোড রাখবো তবে ভিজিটেড দিয়ে আপডেট না করে নতুন এজকে “রিল্যাক্স” বা আপডেট করবো উপরের পদ্ধতিতে। নিচের গ্রাফটা দেখো:
ধরে নেই সোর্স হলো ১ নম্বর নোড। তাহলে
d[1] = 0, d[2] = d[3] = d[4] = infinity(a large value)
ইনফিনিটি কারণ ২,৩,৪ এর দূরত্ব আমরা এখনো জানিনা, আর সোর্সের দূরত্ব অবশ্য শূন্য। এখন তুমি আগের বিএফএস এর মতোই সোর্স থেকে যতগুলো নোডে যাওয়া যায় সেগুলা আপডেট করার চেষ্টা করো, আপডেট করতে পারলে কিউতে পুশ করো। যেমন ১ – ২ এজটা ধরে আমরা আগাবো কারণ $d[1]+2 < d[2]$ এই শর্তটা পূরণ হচ্ছে। তখন $d[2]$ হয়ে যাবে ২, একই ভাবে ১ থেকে ৩ এ গেলে $d[3]$ হয়ে যাবে ৫।
কিন্তু ৫ তো ৩ নম্বরনোডে যাওয়ার শর্টেস্ট ডিসটেন্স না! আমরা বিএফএস এ দেখেছি একটা নোড একবারের বেশি আপডেট হয়না, সেই প্রোপার্টি এখানে কাজ করছেনা। ২ নম্বর নোড থেকে ২-৩ এজ ধরে এগিয়ে আবার আপডেট করলে তখন $d[3]$ তে $d[2] + 1 = 3$ পাবো। তাহলে আমরা দেখলাম এক্ষেত্রে একটা নোড অনেকবার আপডেট হতে পারে। (প্রশ্ন: সর্বোচ্চ কত বার?)
আমরা তাহলে আগের বিএফএস এর সুডোকোডের আপডেট অংশ একটু পরিবর্তন করি যাতে একটা নোড বার বার আপডেট হতে পারে:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
1 procedure BFSmodified(G,source): 2 Q = queue(), distance[] = infinity 3 Q.enqueue(source) 4 distance[source] = 0 5 while Q is not empty 6 u ← Q.pop() 7 for all edges from u to v in G.adjacentEdges(v) do 8 if distance[u] + cost[u][v] < distance[v] 9 distance[v] = distance[u] + cost[u][v] 10 Q.enqueue(v) 11 end if 12 end for 13 end while 14 Return distance |
আমরা ঠিক আগের বিএফএস এর কোডেই জাস্ট কস্ট বসায় বারবার আপডেট করছি! এই কোড তোমাকে সোর্স থেকে প্রতিটা নোডের শর্টেস্ট পাথ বের করে দিবে কিন্তু কমপ্লেক্সিটির দিক থেকে এটা খুবই বাজে! এজন্য আমাদের লাগবে একটা প্রায়োরিটি কিউ।
বিএফএস এ আমরা যখন ১ নোড থেকে অনেকগুলো নোডে যাচ্ছি তখন সেই নোডগুলো থেকে আবার নতুন করে কাজ করার সময় “আগে আসলে আগে পাবেন” ভিত্তিতে কাজ করছি। যেমন উপরের গ্রাফে ১ থেকে আগে ৩ নম্বর নোডে এবং তারপর ২ নম্বর নোডে এ গেলে আগে ৩ নিয়ে কাজ করছি, এরপর ২ নিয়ে কাজ করছি।
ভালো করে দেখো এখানে কি সমস্যাটা হচ্ছে। ৩ নিয়ে আগে কাজ করলে আমরা ৪ এর ডিসটেন্সকে আপডেট করে দিচ্ছি ডিসটেন্স ৫ + ৩ = ৮ হিসাবে। পরবর্তীতে যখন ২ দিয়ে ৩ কে আবার আপডেট করা হচ্ছে তখন ৩ এর ডিসটেন্স হয়ে গিয়েছে ৩, এবার ৪ এর ডিসটেন্সকে আবার আপডেট করছি ৩ + ৩ = ৬ হিসাবে। ৪ কে মোট দুইবার আপডেট করা লাগলো।
বিজ্ঞানী ডায়াক্সট্রা চিন্তা করলেন যদি এই “আগে আসলে আগে পাবেন” ভিত্তিতে কাজ না করে সবথেকে কাছের নোডগুলোকে আগে প্রসেস করি তাহলে অনেক কমবার আপডেট করা লাগে। আমরা যদি ২ কে নিয়ে আগে কাজ করতাম তাহলে ৩ আগেই আপডেট হয়ে যেত এবং ৪ কে একবার আপডেট করেই শর্টেস্ট ডিসটেন্স পেয়ে যেতাম! একটু হাতে কলমে সিমুলেট করে দেখো। আইডিয়াটা হলো যেকোনো সময় কিউ তে যতগুলো নোড থাকবে তাদের মধ্যে যেটা সোর্স থেকে সবথেকে কাছে সেটা নিয়ে আগে কাজ করবো। এজন্যই আমরা কিউ এর জায়গায় বসিয়ে দিবো একটি প্রায়োরিটি কিউ যে কিউতে নোড পুশ করার সাথে সাথে কাছের নোডটাকে সামনে এনে দিবে। পার্থক্য হলো আগে খালি নোড নাম্বার পুশ করেছি, এখন বর্তমান ডিসটেন্স অর্থাত $d[u]$ এর মানটাও পুশ করতে হবে।
নিচে একটা সম্পূর্ণ ডায়াক্সট্রার সুডোকোড দিলাম যেটা ১ থেকে $n$ তম নোডে যাবার শর্টেস্ট পাথ বের করে এবং পাথটাও প্রিন্ট করে:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
1 procedure dijkstra(G, source): 2 Q = priority_queue(), distance[] = infinity 3 Q.enqueue({distance[source], source}) 4 distance[source]=0 5 while Q is not empty 6 u = nodes in Q with minimum distance[] 7 remove u from the Q 8 for all edges from u to v in G.adjacentEdges(v) do 9 if distance[u] + cost[u][v] < distance[v] 10 distance[v] = distance[u] + cost[u][v] 11 Q.enqueue({distance[v], v}) 12 end if 13 end for 14 end while 15 Return distance |
সি++ কোড দেখতে ক্লিক করো এখানে।
এখানে আগের সুডোকোডের থেকে কয়েক জায়গায় একটু ভিন্নতা আছে। এখানে সাধারণ কিউ এর জায়গায় প্রায়োরিটি কিউ ব্যবহার করা হয়েছে। কিউ থেকে পপ হবার সময় তাই সোর্স থেকে এখন পর্যন্ত পাওয়া সবথেকে কাছের নোডটা পপ হচ্ছে এবং সেটা নিয়ে আগে কাজ করছি।
উপরের সুডোকোডে সোর্স থেকে বাকি সব নোডের দূরত্ব বের করা হয়েছে। তুমি যদি শুধু একটা নোডের দুরত্ব বের করতে চাও তাহলে সেটা যখন কিউ থেকে পপ হবে তখনই রিটার্ন করে দিতে পারো।
নেগেটিভ এজ থাকলে কি ডায়াক্সট্রা অ্যালগোরিদম কাজ করবে? যদি নেগেটিভ সাইকেল থাকে তাহলে ইনফিনিট লুপে পরে যাবে, বারবার আপডেট করে কস্ট কমাতে থাকবে। যদি নেগেটিভ এজ থাকে কিন্তু সাইকেল না থাকে তাহলেও কাজ করবেনা। তবে তুমি যদি টার্গেট পপ হবার সাথে সাথে রিটার্ণ করে না দাও তাহলে কাজ করবে কিন্তু সেটা তখন আর মূল ডায়াক্সট্রা অ্যালগোরিদম থাকবেনা।
কমপ্লেক্সিটি:
বিএফএস এর কমপ্লেক্সিটি ছিলো $O(V+E)$ যেখানে $V$ হলো নোড সংখ্যা আর $E$ হলো এজ সংখ্যা। এখানেও আগের মতোই কাজ হবে তবে প্রায়োরিটি কিউ তে প্রতিবার সর্ট করতে $O(logV)$ কমপ্লেক্সিটি লাগবে। মোট: $O(VlogV+E)$ ।
নেগেটিভ সাইকেল নিয়ে কাজ করতে হলে আমাদের জানতে হবে বেলম্যান ফোর্ড অ্যালগোরিদম। সেখানেও এজ রিল্যাক্স করে আপডেট করা হয়, একটা নোডকে সর্বোচ্চ $n – 1$ বার আপডেট করা লাগতে পারে সেই প্রোপার্টি কাজে লাগানো হয়।
ডায়াক্সট্রা ভালো করে শিখতে নিচের প্রবলেমগুলো ঝটপট করে ফেলো:
Dijkstra?
Not the Best
New Traffic System
হ্যাপি কোডিং!
(গ্রাফ থিওরি নিয়ে সবগুলো লেখা)
ফেসবুকে মন্তব্য
Powered by Facebook Comments
Awessome………………….
অসম্ভব সহজ করে লেখা …………
৭ নম্বর লাইনটা বুঝি নাই। দয়াকরে ৭ নম্বর লাইন সম্বন্ধে একটু বিস্তারিত লিখলে কৃতজ্ঞ হতাম।
HI, Jahangir!!
Line 7 is an operator overload. As u need to sort all your data in a Priority_queue , so u need to tell it how it works with Priority_queue q . In this case,line 7 telling us:
bool operator < (const node& p) const {
return p.w < w;
}
it means ' < ' operator will overload a new node p (which will pass through q ) has a cost( we are saving our cost in node.w ). If p.w (the node's cost info ) < w (other nodes current info of cost ) then take node p.w as a priority.
hope it helps!!! 🙂
“ধরো সোর্স থেকে প্রতিটা নোডের ডিসটেন্স রাখা হয়েছে d[] অ্যারেতে।” এটি সম্ভবত সোর্স থেকে প্রতিটা নোডো যাওয়ার কস্ট হবে। এখানে ডিসটেন্স বলতে কি এটাই বোঝানো হয়েছে?
হ্যা এটাই বুঝানো হয়েছে।
Vaiya, I can’t understand how 63 works as a huge value in d[] array memset. Can you plz clarify it ?
I want to know about this 63
memset(d,63,sizeof(d)); // How 63 works as huge value ?
63 এর বাইনারি হলো 111111, ৮বিট আকারে লিখলে 00111111। এখন d অ্যারেতে বিট আছে 32*array_size সংখ্যক। 63 দিয়ে মেমসেট করলে প্রথমে সবগুলো বিটকে ৮বিটের কিছু ব্লকে ভাগ করা হবে, অনেকটা এরকম:
প্রতি এলিমেন্টে যেমন d[0] তে থাকে ৩২টা বিট বা ৪টা ৮বিটের ব্লক। এখন প্রতি ব্লকে ৬৩ বসিয়ে দাও। d[0] এর চেহারা হয়ে যাবে ঠিক এরকম:
এই সংখ্যাটাই হলো 1061109567 বা আমাদের দরকারি “অনেক বড়” একটা সংখ্যা! একইভাবে তুমি যদি ৩১ দিয়ে মেমসেট করতে তাহলে পাবে প্রতি এলিমেন্টে পাবে এরকম:
এখন কি বলতে পারবে -১ দিয়ে মেমসেট করলে প্রতিঘরে কিভাবে -১ পাওয়া যায়? 🙂
bool operator < কি ? ( ২য় কোডে )
“bool operator <" হবে ওটা। < অপারেটরকে ওভারলোড করা হচ্ছে।
ভুলে O(V+E) এর পরিবর্তে বিএফএস এর কমপ্লেক্সিটি ছিলো log(V+E) লেখা হয়েছে, dijkstra এর ক্ষেত্রেও log(VlogV+E) এর পরিবর্তে O(VlogV+E) হবে।
ভাইয়া সেকন্ড শর্টেস্ট পাথের প্রব্লেম গুলো কিভাবে সল্ভ করা যেতে পারে ??
bro…. i can’t understand line 7……
bool operator < ( const node& p ) const { return w > p.w; }
what is the necessity of this line???
Search for operator overloading in google.
এখানে অপারেটর ওভারলডিং কেন ব্যবহার করা হল ??
আবার অপারেটর ওভারলডিং না করে শুধু (less than) “<" ব্যবহার করলে ইরর দেয়।
অপারেটর ওভারলডিং ব্যবহার করা হয় যখন কোন ক্লাসের অবজেক্ট এর মধ্যে ক্যালকুলেশন করা হয় ।
কিন্তু এখানে if(d[u]+cost[u][i]<d[v]) যেখানে d,cost,v,u integer. Structure variable নয় ।
তাই ঠিক বুঝতে সমস্যা হছে ।
[আমার অপারেটর ওভারলডিং বিস্তৃত ভাবে এখন ও জানি না । যেটুকু জানি সেটা থেকেই প্রশ্ন আসছে মনে । ]
ভাইয়া এই লাইনটা কি ঠিক আছে???
distance[u]=distance[v]+1;???
এইটা হওয়া উচিত না??
distance[v]=distance[u]+cost[u][v];
স্যার এখানে Operator overloading টা কিভাবে কাজ করতেছে বুঝতেছিনা ?
যখন ২ দিয়ে ৩ কে আবার আপডেট করা হচ্ছে তখন ৩ এর ডিসটেন্স হয়ে গিয়েছে ৩, এবার ৪ এর ডিসটেন্সকে আবার আপডেট করছি ৩ + ৩ = ৫ হিসাবে।
৩ + ৩ = ৫??
ভাইয়া, operator overloading নিয়ে একটা লেখা লিখলে ভালো হতো। operator overloading নিয়ে ভাল কোনো রিসোর্স পাচ্ছি না।