Skip to content

022 — Cheapest Flights Within K Stops

Source

  • Original source: Hop-limited shortest-path-এর classic প্রয়োগ
  • Platform: LeetCode — https://leetcode.com/problems/cheapest-flights-within-k-stops/
  • 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)

1. Problem in simple words

তোমাকে n টা শহর আর কতগুলো flight দেওয়া আছে; প্রতিটা flight [from, to, price] মানে from শহর থেকে to শহরে ওই দামে যাওয়া যায় (একমুখী)। তোমাকে src থেকে dst-এ যেতে হবে, কিন্তু শর্ত — মাঝে সবচেয়ে বেশি k টা stop (থামা) নিতে পারো, অর্থাৎ সবচেয়ে বেশি k+1 টা flight নিতে পারো। এই সীমার মধ্যে সবচেয়ে কম মোট দাম বের করো; না পারলে -1।

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

2. Which basic idea does this inherit from?

এটা দাঁড়িয়ে Bellman-Ford-এর pass-structure-এর উপর (../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 সরাসরি বলে: "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 বেছে নেওয়া)।

6. Real-life analogy

ভাবো তোমার কাছে শহরগুলোর সবচেয়ে সস্তা ভাড়ার একটা বোর্ড আছে, আর প্রতিদিন সকালে তুমি বোর্ডটা update করো — কিন্তু নিয়ম: আজকের update করতে গতকালের লেখা দামগুলোই দেখবে, আজ এইমাত্র বদলানো দাম নয়। দিন 1-এ এক flight দূরত্বের সস্তা দাম জানা যায়, দিন 2-এ দুই flight, ... দিন k+1-এ সর্বোচ্চ k+1 flight-এর সস্তা দাম। k+1 দিন পরে বোর্ডে dst-এর দামই উত্তর। "গতকালের বোর্ড দেখা" = snapshot।

7. Visual explanation

n=3, flights=[0->1:100, 1->2:100, 0->2:500], src=0, dst=2, k=1:

শুরু 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)

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: DFS/recursion দিয়ে src থেকে সব পথ ঘোরো, সাথে "এখন পর্যন্ত কত stop নিয়েছি" বহন করো; stop-সংখ্যা k ছাড়ালে থামো, dst-এ পৌঁছালে মোট দাম candidate-এ রাখো, সবচেয়ে ছোটটা রাখো।

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 বেছে দেয়।

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।

15. Python solution

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।

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!।

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 করে দেয়।

21. Which basic problem this inherits from

ভিত্তি: Bellman-Ford (../shortest-path.md-এর shortest-path table)। আটকে গেলে আগে Bellman-Ford-এর মূল সত্যটা মনে করো: "i pass-এর পর ≤ i edge-এর সবচেয়ে ছোট path সঠিক।" এই problem তারই সরাসরি প্রয়োগ — শুধু pass-সংখ্যা hop-limit-এ কেটে দেওয়া। অর্ধেক উত্তর shortest-path.md-এই আছে।

22. Similar harder problems

23. Pattern learned

Bellman-Ford pass with hop limit: "at most k edges/stops"-এর সবচেয়ে সস্তা path চাইলে Bellman-Ford-এর pass-সংখ্যা ঠিক k+1-এ কাটো, আর প্রতি pass-এ আগের pass-এর snapshot থেকে relax করো।

24. Final summary

ভবিষ্যতের আমাকে: "Cheapest Flights = hop-limited Bellman-Ford; k+1 pass, প্রতি pass-এ snapshot=dist[:] থেকে relax (in-place নয়), শেষে dist[dst] বা -1।" 'shortest cost with at most k hops/stops' দেখলেই pass-structure (Dijkstra নয়) মনে পড়বে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।