Problem link ও উৎস
- **Original source:** Hop-limited shortest-path-এর classic প্রয়োগ
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Hard
- **Pattern:** Bellman-Ford passes (at most k+1 edges পর্যন্ত relax)
- **Basic idea inherited from:** shortest-path table — Bellman-Ford (দেখো [../shortest-path.md](../shortest-path.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে `n` টা শহর আর কতগুলো flight দেওয়া আছে; প্রতিটা flight `[from, to, price]` মানে `from` শহর থেকে `to` শহরে ওই দামে যাওয়া যায় (একমুখী)। তোমাকে `src` থেকে `dst`-এ যেতে হবে, কিন্তু শর্ত — মাঝে সবচেয়ে বেশি `k` টা **stop** (থামা) নিতে পারো, অর্থাৎ সবচেয়ে বেশি `k+1` টা flight নিতে পারো। এই সীমার মধ্যে সবচেয়ে কম মোট দাম বের করো; না পারলে -1।
```text
n=4, flights = [0->1:100, 1->2:100, 2->0:100, 1->3:600, 2->3:200]
src=0, dst=3, k=1 (সর্বোচ্চ 1 stop = 2 flight)
0->1->3 : 100+600 = 700 (1 stop) <- বৈধ
0->1->2->3 : 100+100+200 = 400 (2 stop) <- সস্তা কিন্তু 2 stop, k=1-এ অবৈধ
উত্তর: 700
```
### Input ও output {#8-example-input-and-output}
```text
Input : n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1
Output: 700
Input : n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output: 200
Edge case (k=0, সরাসরি flight নেই): same n=3 list, k=0 -> 500
Edge case (পৌঁছানোই যায় না): n=3, flights=[[0,1,5]], src=0, dst=2, k=5 -> -1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার কাছে শহরগুলোর সবচেয়ে সস্তা ভাড়ার একটা বোর্ড আছে, আর প্রতিদিন সকালে তুমি বোর্ডটা update করো — কিন্তু নিয়ম: আজকের update করতে গতকালের লেখা দামগুলোই দেখবে, আজ এইমাত্র বদলানো দাম নয়। দিন 1-এ এক flight দূরত্বের সস্তা দাম জানা যায়, দিন 2-এ দুই flight, ... দিন `k+1`-এ সর্বোচ্চ `k+1` flight-এর সস্তা দাম। `k+1` দিন পরে বোর্ডে `dst`-এর দামই উত্তর। "গতকালের বোর্ড দেখা" = snapshot।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে **Bellman-Ford**-এর pass-structure-এর উপর ([../shortest-path.md](../shortest-path.md)-এর shortest-path table)। Bellman-Ford সব edge `V-1` বার relax করে কারণ সবচেয়ে ছোট path-এ বড়জোর `V-1` টা edge থাকে। এই problem-এ edge-সংখ্যাই সীমিত — সর্বোচ্চ `k+1`। তাই Bellman-Ford-এর ঠিক `k+1` টা pass চালালেই "সর্বোচ্চ k+1 edge ব্যবহার করা সবচেয়ে সস্তা পথ" বেরিয়ে আসে। [../shortest-path.md](../shortest-path.md) সরাসরি বলে: "K-pass structure-টা 'cheapest with at most k hops' problem-ও solve করে।"
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: Bellman-Ford-এর pass-সংখ্যা আর edge-সংখ্যার সম্পর্ক। **i-তম pass-এর পর, ≤ i টা edge ব্যবহার করা প্রতিটা সবচেয়ে ছোট path ঠিকঠাক হিসাব হয়ে যায়।** তাই hop limit থাকলে আমরা শুধু pass-সংখ্যা সেই limit-এ কেটে দিই। কিন্তু একটা সূক্ষ্ম জিনিস: প্রতিটা pass-এ relax করতে হবে **আগের pass-এর** distance থেকে, একই pass-এর তাজা update থেকে নয় — নাহলে এক pass-এই multiple edge "লিক" করে hop-গণনা ভুল হয়ে যাবে। এই জন্য প্রতি pass-এ distance-এর একটা snapshot নিই।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
মূলত একটা **distance array** (`dist[i]` = src থেকে শহর i-তে এখন পর্যন্ত জানা সবচেয়ে কম দাম) আর প্রতি pass-এ তার একটা **copy/snapshot**। edges শুধু list আকারে ঘুরলেই চলে; আলাদা adjacency বাধ্যতামূলক নয় (যদিও বিকল্প Dijkstra-ধাঁচ সমাধানে adjacency + min-heap লাগে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
distance array + snapshot fit করে কারণ Bellman-Ford-এর গোটা কাজই হলো "প্রতি pass-এ সব edge দেখে dist improve করো", আর hop-limit ঠিক রাখতে দরকার "এই pass শুধু আগের pass পর্যন্ত জানা দূরত্ব দেখুক"। snapshot সেই isolation দেয়, যাতে এক pass-এ একটার বেশি edge না gলে। heap এখানে দরকার নেই, কারণ আমরা cheapest-first greedy নয় — fixed সংখ্যক full pass চালাচ্ছি (greedy hop-limit-এ ভেঙে যায়, তাই Bellman-Ford বেছে নেওয়া)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: DFS/recursion দিয়ে `src` থেকে সব পথ ঘোরো, সাথে "এখন পর্যন্ত কত stop নিয়েছি" বহন করো; stop-সংখ্যা `k` ছাড়ালে থামো, `dst`-এ পৌঁছালে মোট দাম candidate-এ রাখো, সবচেয়ে ছোটটা রাখো।
```text
1) dfs(node, stops_left, cost_so_far)
2) node == dst -> answer = min(answer, cost_so_far)
3) stops_left < 0 -> থামো
4) প্রতিটা outgoing flight ধরে dfs(to, stops_left-1, cost+price)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
hop-limit সহ exhaustive DFS exponential হয়ে যেতে পারে — একই (node, stops_left) state বহু ভিন্ন পথ ধরে আবার আবার explore হয়, প্রতিবার নতুন করে সাব-পথ গোনা হয়। memoization ছাড়া এটা ভয়ংকর redundant; আর memo যোগ করলে আসলে সেটা Bellman-Ford/Dijkstra-ধাঁচেই রূপ নেয়। মূল অপচয়: "k হপে node X-এ সস্তা দাম" বারবার নতুন করে হিসাব করা, যেখানে সেটা একবার বের করে রেখে দেওয়াই যথেষ্ট।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: hop limit = edge limit। সবচেয়ে ছোট path-এ যত edge, ঠিক ততবার Bellman-Ford pass চালালে সেই path ধরা পড়ে। তাই সাধারণ Bellman-Ford-এর `V-1` pass-কে কেটে `k+1` pass-এ থামাও — পাবে "সর্বোচ্চ k+1 edge-এর সবচেয়ে সস্তা পথ", যা ঠিক "সর্বোচ্চ k stop"-এর সমান।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`k+1` বার সব edge relax করো। প্রতি pass শুরুতে `dist`-এর একটা snapshot নাও, আর relax-এর সময় snapshot থেকে পড়ো কিন্তু আসল `dist`-এ লেখো। এতে নিশ্চিত হয় যে এক pass-এ একটার বেশি edge ব্যবহার হয় না (hop-গণনা ঠিক থাকে)। `k+1` pass শেষে `dist[dst]` infinity না হলে সেটাই উত্তর, নাহলে -1। (Greedy/Dijkstra সরাসরি hop-limit-এ unsafe হতে পারে কারণ "k হপে সস্তা" আর "সস্তা" এক নয় — তাই pass-structure বেছে নিই।)
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "shortest path" দেখে সরাসরি Dijkstra-তে ঝাঁপিয়ে পোড়ো না — "at most k hops" শব্দটা তোমাকে edge-গোনার দিকে ঠেলছে, আর edge গোনার tool হলো Bellman-Ford-এর pass। `sum` minimize নয়, "k pass-এর মধ্যে যত সস্তা হয়" — limit-টাই algorithm বেছে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`n=3, flights=[0->1:100, 1->2:100, 0->2:500], src=0, dst=2, k=1`:
```text
শুরু dist: [0, INF, INF]
pass 1 (snapshot=[0,INF,INF]):
0->1:100 dist[1]=0+100=100
1->2:100 snapshot[1]=INF, skip
0->2:500 dist[2]=0+500=500
dist: [0, 100, 500]
pass 2 (snapshot=[0,100,500]): <- k+1 = 2 pass
0->1:100 100, উন্নতি নেই
1->2:100 snapshot[1]=100 -> dist[2]=min(500,200)=200
0->2:500 উন্নতি নেই
dist: [0, 100, 200]
dist[2] = 200 -> উত্তর (0->1->2, 1 stop)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1` (উত্তর 200):
1. `dist=[0, INF, INF]`। pass চলবে `k+1=2` বার।
2. **pass 1**, `snapshot=[0,INF,INF]`: `0->1` → `dist[1]=100`; `1->2` snapshot[1]=INF, skip; `0->2` → `dist[2]=500`। এখন `dist=[0,100,500]`।
3. **pass 2**, `snapshot=[0,100,500]`: `0->1` উন্নতি নেই; `1->2` snapshot[1]=100 → `dist[2]=min(500,200)=200`; `0->2` উন্নতি নেই। এখন `dist=[0,100,200]`।
4. `dist[dst]=dist[2]=200` ≠ INF → return `200`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
import heapq
def cheapest_flights(n, flights, src, dst, k):
# Bellman-Ford ধাঁচে: ঠিক k+1 pass, প্রতিবার পুরোনো dist থেকে relax
INF = float("inf")
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1): # at most k stops = k+1 edges
snapshot = dist[:] # এই pass-এর update শুধু আগের pass-এর দাম দেখুক
for u, v, w in flights:
if snapshot[u] != INF and snapshot[u] + w < dist[v]:
dist[v] = snapshot[u] + w # relax
return dist[dst] if dist[dst] != INF else -1
def cheapest_flights_dijkstra(n, flights, src, dst, k):
# বিকল্প: stops সহ Dijkstra-ধাঁচ, (cost, node, stops_used)
adj = defaultdict(list)
for u, v, w in flights:
adj[u].append((v, w))
heap = [(0, src, 0)] # (cost, node, এখন পর্যন্ত নেওয়া stop)
best = {}
while heap:
cost, node, stops = heapq.heappop(heap)
if node == dst:
return cost
if stops > k:
continue
if best.get((node, stops), float("inf")) < cost:
continue
for nxt, w in adj[node]:
nc = cost + w
if nc < best.get((nxt, stops + 1), float("inf")):
best[(nxt, stops + 1)] = nc
heapq.heappush(heap, (nc, nxt, stops + 1))
return -1
# ---- tests ----
f1 = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
assert cheapest_flights(4, f1, 0, 3, 1) == 700
f2 = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
assert cheapest_flights(3, f2, 0, 2, 1) == 200
assert cheapest_flights(3, f2, 0, 2, 0) == 500
assert cheapest_flights(3, [[0, 1, 5]], 0, 2, 5) == -1
assert cheapest_flights_dijkstra(4, f1, 0, 3, 1) == 700
assert cheapest_flights_dijkstra(3, f2, 0, 2, 1) == 200
assert cheapest_flights_dijkstra(3, f2, 0, 2, 0) == 500
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dist = [INF]*n; dist[src]=0` — src ছাড়া সব শহর শুরুতে অজানা দূরত্ব।
- `for _ in range(k+1)` — সর্বোচ্চ k stop মানে সর্বোচ্চ k+1 edge, তাই ঠিক k+1 pass।
- `snapshot = dist[:]` — মূল চাবি: এই pass শুধু আগের pass-এর দাম দেখবে, যাতে এক pass-এ একাধিক edge না gলে।
- `if snapshot[u] != INF and snapshot[u]+w < dist[v]` — u-তে পৌঁছানো গেছে এবং u হয়ে v-তে গেলে সস্তা হলে relax।
- `dist[v] = snapshot[u] + w` — improved দাম আসল dist-এ লেখো (snapshot-এ নয়)।
- `return dist[dst] if ... else -1` — k+1 pass শেষে dst এখনও INF হলে অসম্ভব, নাহলে সেই দাম।
- বিকল্প function-এ `(cost, node, stops)` heap — Dijkstra-ধাঁচ কিন্তু state-এ stop-সংখ্যা যোগ করা, `best[(node,stops)]` দিয়ে stale skip।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cheapest_flights(4, f1, 0, 3, 1)`: pass 1-এ `0->1` দেয় `dist[1]=100`; pass 2-এ snapshot থেকে `1->3` দেয় `dist[3]=700`। সস্তা `0->1->2->3` (400) লাগে 2 stop, কিন্তু সেটা পেতে 3 pass লাগত — k+1=2 pass-এ আটকে যাওয়ায় ধরা পড়ে না, ঠিক যেমন চাই। `dist[3]=700` → return 700। বাকি assert (দুই function-ই) pass, শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(k · E)** — k+1 টা pass, প্রতি pass-এ সব E টা edge একবার। hop-limit ছোট হলে এটা সাধারণ Bellman-Ford (`O(V·E)`)-এর চেয়েও সস্তা।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(V)** — `dist` array আর প্রতি pass-এ তার একটা snapshot, দুটোই শহর-সংখ্যার সমান। edges input বাদে কোনো বড় structure নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- snapshot ছাড়া in-place relax করা — তখন এক pass-এ একাধিক edge gলে hop-গণনা ভুল হয়, উত্তর বেশি কম আসে।
- `k+1`-এর বদলে `k` বার pass চালানো — এক hop কম, সঠিক সস্তা path miss।
- সাধারণ Dijkstra চালিয়ে hop উপেক্ষা করা — hop-limit থাকায় cheapest-first greedy ভুল উত্তর দিতে পারে।
- `dst` অপৌঁছানো অবস্থায় INF return করা, -1 না দেওয়া।
- বিকল্প Dijkstra-ধাঁচে `(node, stops)` ছাড়া শুধু `node` visited mark করা — তখন কম-cost-বেশি-stop entry সঠিক সমাধান block করে দেয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: **Bellman-Ford** ([../shortest-path.md](../shortest-path.md)-এর shortest-path table)। আটকে গেলে আগে Bellman-Ford-এর মূল সত্যটা মনে করো: "i pass-এর পর ≤ i edge-এর সবচেয়ে ছোট path সঠিক।" এই problem তারই সরাসরি প্রয়োগ — শুধু pass-সংখ্যা hop-limit-এ কেটে দেওয়া। অর্ধেক উত্তর `shortest-path.md`-এই আছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Network Delay Time (hop-limit ছাড়া, সাধারণ Dijkstra) —