Dijkstra's Algorithm
Single Source Shortest Path (SSSP) বের করার একটি greedy অ্যালগরিদম — ধারণা থেকে শুরু করে, ধাপে ধাপে, পরীক্ষার ফরম্যাটে সমাধান পর্যন্ত।
লাইভ ডেমো — Relaxation কীভাবে কাজ করে দেখো
Graph: A→B=4, A→C=1, C→B=2, B→D=5, C→D=8, D→E=3পূর্বশর্ত ধারণাগুলো
Dijkstra বোঝার আগে এই টার্মগুলো ক্লিয়ার থাকা দরকার। প্রতিটায় ক্লিক করো।
গ্রাফ (Graph) কী?
গ্রাফ মানে হলো কিছু বিন্দু (vertex/node) আর সেগুলোর মধ্যে সংযোগ (edge)।
উদাহরণ: ঢাকা, কুমিল্লা, চট্টগ্রাম — প্রত্যেকটা শহর একটা vertex, দুই শহরের মধ্যের রাস্তা একটা edge।
ওজনযুক্ত গ্রাফ (Weighted Graph) কী?
প্রত্যেকটা edge-এর উপর যদি একটা সংখ্যা (cost/distance/time) লেখা থাকে, তাহলে সেটা weighted graph। এই weight distance, time, বা cost — যেকোনো কিছু হতে পারে। আমরা চাই সবচেয়ে কম cost-ওয়ালা পথ বের করতে।
Directed বনাম Undirected গ্রাফ
Directed: edge-এর একটা দিক (তীর চিহ্ন) থাকে। A→B মানে A থেকে B-তে যাওয়া যায়, উল্টো দিকে না।
Undirected: edge-এর কোনো দিক নেই। A–B মানে দুই দিকেই যাওয়া যায়। cost হিসাব করার সময় দিক matter করে, তাই এটা মনে রাখা জরুরি।
উৎস বিন্দু (Source Vertex) কী?
যেখান থেকে শুরু করছি, সেটা source। Dijkstra একটা fixed source থেকে শুরু হয়ে বাকি সব vertex পর্যন্ত shortest distance বের করে।
কেন Dijkstra দরকার?
সরাসরি edge মানেই সেটা shortest path না — ঘুরে গেলে কম পড়তে পারে। তাই শুধু একটা edge দেখে shortest বলা যায় না, সবকিছু systematically check করতে হয়। এই systematic checking-টাই Dijkstra করে।
"রিল্যাক্সেশন (Relaxation)" কী?
একটা edge দিয়ে গেলে current distance-এর চেয়ে কম পাওয়া যায় কিনা চেক করা, আর কম পেলে update করা। সহজ কথায়: "আরও ভালো (কম) রাস্তা পেলে আগেরটা ভুলে নতুনটা ধরো।"
"সিলেক্টেড/ফাইনালাইজড ভার্টেক্স" কী?
যখন একটা vertex select হয়, তার distance ফাইনাল হয়ে যায় — আর কখনো বদলাবে না। এটাই Dijkstra-র greedy স্বভাব: প্রতি ধাপে সবচেয়ে কম দূরত্বওয়ালা vertex-কে নিশ্চিত ধরে নেওয়া হয়।
পরীক্ষার সংজ্ঞা
Definition (English — exam-ready)
Dijkstra's Algorithm is a greedy algorithm used to find the Single Source Shortest Path (SSSP) in a weighted graph (with non-negative edge weights) from a given source vertex to all other vertices. At each step, it selects the unvisited vertex with the minimum tentative distance, marks it as finalized (selected), and relaxes all of its outgoing edges to update the distances of its neighboring vertices.
মূল সূত্র (Relaxation condition)
d[v] = d[u] + c(u,v)
d[u] = u পর্যন্ত এখন পর্যন্ত জানা সবচেয়ে কম দূরত্ব · c(u,v) = u→v edge-এর weight · d[v] = v পর্যন্ত এখন পর্যন্ত জানা সবচেয়ে কম দূরত্ব
অ্যালগরিদম ধাপে ধাপে
Initialization
Source-এর d[source] = 0, বাকি সব vertex-এর দূরত্ব ∞ ধরা হয়।
কেন: শুরুতে আমাদের কোনো তথ্য নেই, তাই "অজানা"-কে ∞ দিয়ে represent করি।
সবচেয়ে কম d[] ওয়ালা unselected vertex select করো
যেসব vertex এখনো select হয়নি, তাদের মধ্যে সবচেয়ে কম দূরত্বওয়ালাটা নাও।
কেন: এটাই greedy choice — negative weight না থাকলে এটাই নিশ্চিতভাবে সবচেয়ে কম।
Selected vertex-কে "final" মার্ক করো
এই vertex-এর d[] মান এখন থেকে আর কখনো বদলাবে না।
কেন: কাজ সহজ রাখার জন্য — আমরা জানি এটাই সবচেয়ে কম, তাই re-check দরকার নেই।
সব outgoing edge দিয়ে Relaxation করো
Selected vertex u থেকে প্রতিটা edge (u→v)-এর জন্য চেক করো:
কেন: u হয়ে v-তে গেলে যদি current দূরত্বের চেয়ে কম হয়, সেটাই এখন পর্যন্ত সেরা path।
সব vertex select না হওয়া পর্যন্ত repeat করো
ধাপ ১–৩ বারবার করো যতক্ষণ না সব vertex "selected" হয়।
কেন: প্রত্যেকটা vertex-কে একবার করে finalize করা লাগবে।
Terminate
d[] array-তে প্রতিটা vertex-এর shortest distance পাওয়া যাবে। Path দরকার হলে via/parent থেকে backtrack করো।
সমাধান করা প্রশ্ন — ১
নিচের directed graph-টি লক্ষ কর: A→B=4, A→C=1, C→B=2, B→D=5, C→D=8, D→E=3। Dijkstra's Algorithm প্রয়োগ করে source A থেকে প্রতিটি vertex-এর shortest distance নির্ণয় কর। Selected Vertex Table দেখাও এবং প্রতিটি vertex-এ পৌঁছানোর path লেখো।
Selected Vertex Table
| Step | Selected | d[A] | d[B] | d[C] | d[D] | d[E] |
|---|---|---|---|---|---|---|
| 0 | init | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A (0) | 0 | 4 | 1 | ∞ | ∞ |
| 2 | C (1) | 0 | 3 | 1 | 9 | ∞ |
| 3 | B (3) | 0 | 3 | 1 | 8 | ∞ |
| 4 | D (8) | 0 | 3 | 1 | 8 | 11 |
| 5 | E (11) | 0 | 3 | 1 | 8 | 11 |
ধাপে ধাপে ব্যাখ্যা
ধাপ ১ — A সিলেক্ট (d=0): A→B: 0+4=4<∞ ✓ → d[B]=4। A→C: 0+1=1<∞ ✓ → d[C]=1। পরে কম C(1), তাই পরেরবার C সিলেক্ট হবে।
ধাপ ২ — C সিলেক্ট (d=1): C→B: 1+2=3<4 ✓ → d[B] আপডেট: ৪→৩! C→D: 1+8=9<∞ ✓ → d[D]=9। এটাই মূল পয়েন্ট — সরাসরি A→B(4) থেকে ঘুরে A→C→B(3) কম।
ধাপ ৩ — B সিলেক্ট (d=3): B→D: 3+5=8<9 ✓ → d[D] আপডেট: ৯→৮।
ধাপ ৪ — D সিলেক্ট (d=8): D→E: 8+3=11<∞ ✓ → d[E]=11।
ধাপ ৫ — E সিলেক্ট (d=11): কোনো outgoing edge নেই। সমাধান শেষ।
চূড়ান্ত উত্তর
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| Distance from A | 0 | 3 | 1 | 8 | 11 |
| Path | A | A→C→B | A→C | A→C→B→D | A→C→B→D→E |
💡 সরাসরি A→B = 4, কিন্তু ঘুরে A→C→B = 3, কম। তাই "সরাসরি edge মানেই shortest" — এই ধারণা ভুল।
সমাধান করা প্রশ্ন — ২
একটি directed weighted graph দেওয়া আছে যার edge গুলো হলো: S→A=10, S→C=3, C→A=4, A→B=2, C→B=8, C→D=2, B→D=1, D→B=1। Dijkstra's Algorithm প্রয়োগ করে source S থেকে সবগুলো vertex-এর shortest distance বের কর। উত্তরে Selected Vertex Table দেখাতে হবে এবং S থেকে B পর্যন্ত shortest path উল্লেখ করতে হবে।
সমাধান দেখাও (Show Solution)
Selected Vertex Table
| Step | Selected | d[S] | d[A] | d[B] | d[C] | d[D] |
|---|---|---|---|---|---|---|
| 0 | init | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | S (0) | 0 | 10 | ∞ | 3 | ∞ |
| 2 | C (3) | 0 | 7 | 11 | 3 | 5 |
| 3 | D (5) | 0 | 7 | 6 | 3 | 5 |
| 4 | B (6) | 0 | 7 | 6 | 3 | 5 |
| 5 | A (7) | 0 | 7 | 6 | 3 | 5 |
ব্যাখ্যা
S সিলেক্ট (0): S→A: 0+10=10<∞ ✓ · S→C: 0+3=3<∞ ✓
C সিলেক্ট (3, কম): C→A: 3+4=7<10 ✓ আপডেট · C→B: 3+8=11<∞ ✓ · C→D: 3+2=5<∞ ✓
D সিলেক্ট (5, কম): D→B: 5+1=6<11 ✓ আপডেট
B সিলেক্ট (6, কম): B→D: 6+1=7, কিন্তু d[D]=5, 7<5 না → আপডেট হবে না
A সিলেক্ট (7): A→B: 7+2=9, কিন্তু d[B]=6, 9<6 না → আপডেট হবে না
চূড়ান্ত উত্তর
| Vertex | S | A | B | C | D |
|---|---|---|---|---|---|
| Distance from S | 0 | 7 | 6 | 3 | 5 |
| Path | S | S→C→A | S→C→D→B | S→C | S→C→D |
S→B path: B-এর via = D, D-এর via = C, C-এর via = S → S→C→D→B, cost = 3+2+1 = 6। (A হয়ে গেলে S→C→A→B = 3+4+2 = 9, অনেক বেশি।)
প্রশ্ন — ৩ (Undirected Graph)
Undirected weighted graph-এ Dijkstra's Algorithm প্রয়োগ করার নিয়ম ব্যাখ্যা কর।
সমাধান দেখাও (Show Solution)
নিয়ম: প্রতিটা undirected edge u–v(w)-কে দুইটা directed edge হিসেবে ধরতে হবে:
কেন: undirected edge মানে দুই দিকেই যাওয়া যায়, তাই relaxation করার সময় দুই দিক থেকেই চেক করতে হবে।
বাস্তবে: একটা vertex সিলেক্ট হওয়ার পর তার সব প্রতিবেশী দেখতে হবে (edge কোন দিকে লেখা তা matter করে না), তারপর সাধারণ Dijkstra পদ্ধতি অনুসরণ করতে হবে।
প্রশ্ন — ৪ (থিওরি, প্রতিটি ★১)
Time complexity কত?
Array দিয়ে minimum খুঁজলে: O(V²)। Min-heap (priority queue) ব্যবহার করলে: O((V+E) log V)।
Negative edge weight-এ কাজ করে কি?
না। একবার vertex select (finalize) হয়ে গেলে Dijkstra ধরে নেয় সেটার distance ফাইনাল। Negative weight থাকলে পরে finalized vertex দিয়ে আরও কম distance পাওয়া যেতে পারে, কিন্তু Dijkstra সেটা ঠিক করবে না। এক্ষেত্রে Bellman-Ford Algorithm লাগে (এই syllabus-এ নেই)।
Dijkstra কোন ধরনের অ্যালগরিদম?
এটা একটা Greedy Algorithm — প্রতি ধাপে locally optimal choice নেয় (সবচেয়ে কম known distance-ওয়ালা unvisited vertex)।
SSSP মানে কী?
Single Source Shortest Path — একটা নির্দিষ্ট source vertex থেকে গ্রাফের বাকি সব vertex পর্যন্ত shortest distance বের করা।
সাধারণ ভুলগুলো
<-এর বদলে ≤ দিয়ে করা — শুধু strictly কম হলেই update করবে।∞ + 5 = ∞, বাস্তব path না পাওয়া পর্যন্ত।প্র্যাকটিস প্রশ্ন — নিজে করো
সমাধান দেওয়া হয়নি ইচ্ছাকৃতভাবে। Selected Vertex Table বানিয়ে ধাপে ধাপে relaxation করো।
S→A=2, S→B=5, A→C=6, A→B=1, B→D=4, C→D=1, C→E=2, D→E=3
Source = S। সব vertex-এর shortest distance ও path বের কর।
A→B=3, A→C=6, B→C=2, B→D=8, C→D=1, C→E=4, D→E=2
Source = A। Selected Vertex Table সহ সব ধাপ দেখাও।
A→B=1, A→C=4, B→C=1, B→D=6, C→D=1, D→E=1, E→C=1
Source = A। সব weight positive — cycle থাকলেও Dijkstra কীভাবে চলে লক্ষ কর।
Vertices: P, Q, R, S, TP–Q=4, P–R=1, R–Q=2, Q–S=5, R–S=8, S–T=3
Source = P। আগে প্রতিটা edge-কে directed বানাও।
১. Dijkstra-কে কেন "greedy" বলা হয়, নিজের ভাষায় লেখো। ২. এমন একটা গ্রাফ বানাও যেখানে ঘোরা path shortest। ৩. Dijkstra ও Bellman-Ford-এর মূল পার্থক্য কী?