কনটেন্টে যান

019 — Shortest Routes I

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

n টা city (1 থেকে n) আর m টা directed road আছে; প্রতিটা road (a, b, w) মানে "city a থেকে city b-তে যেতে w খরচ" (একমুখী, weight w)। তুমি city 1-এ আছো। বের করো প্রতিটা city-তে পৌঁছানোর সবচেয়ে কম খরচ, আর n টা সংখ্যা ছাপাও (city 1 থেকে city 1..n-এর shortest distance)। এটাই textbook Dijkstra, এবার CP scale-এ (n 10^5 অবধি, m 2·10^5 অবধি, distance long-এ যেতে পারে)।

উদাহরণ
source = city 1
প্রতিটা city-র জন্য shortest distance বের করো
output: city 1 থেকে city n পর্যন্ত প্রতিটি dist[i], city index-এর ক্রমে
(সব city reachable ধরা হয় এই problem-এ)

Input ও output

উদাহরণ
Input : n=4, roads=[(1,2,5),(1,3,2),(3,2,1),(2,4,3),(3,4,7)], source=1
Output: [0, 3, 2, 6]    (city 1..4-এর shortest distance; 1->3->2->4 = 6)

Input : n=2, roads=[(1,2,7)], source=1
Output: [0, 7]

Edge case (একা node): n=1, roads=[], source=1 -> [0]

চেনা উদাহরণে বোঝা

একটা ডেলিভারি hub (city 1) থেকে প্রতিটা শহরে পৌঁছানোর সবচেয়ে সস্তা পথ বের করছ ভাবো, প্রতিটা রাস্তায় আলাদা খরচ। হাতে একটা তালিকা: "যেসব শহরে পৌঁছানো যায়, তাদের সর্বনিম্ন জানা খরচসহ।" সবসময় সবচেয়ে কম খরচের শহরটা আগে চূড়ান্ত করো — বাকিদের খরচ এখন এর সমান বা বেশি, আর সামনে রাস্তা কেবল যোগ করবে। সেই শহরে পৌঁছে তার বেরোনো রাস্তাগুলো দিয়ে নতুন খরচ হিসাব করো (relax), আবার সবচেয়ে সস্তাটা নাও। শহর অনেক হলেও (CP scale) এই greedy পদ্ধতি দ্রুত — শুধু "এই হিসাবটা তো আগেই সস্তায় করেছি" এমন পুরোনো এন্ট্রি এলে বাদ দাও।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো #18 Network Delay Time (018-network-delay-time.md) — হুবহু Dijkstra: min-heap-এ (cost, node), সবচেয়ে সস্তা pop করো (distance final), edges relax করে push, stale entry skip (lazy deletion)। ../shortest-path.md-এর সূত্র Dijkstra = BFS + greedy + heap এখানে সরাসরি প্রযোজ্য। নতুন কিছু নেই algorithm-এ; পার্থক্য শুধু scale — বড় n, m, তাই lazy-skip লাইনটা এখানে performance-এর জন্য বাধ্যতামূলক, আর distance overflow এড়াতে বড় INF।

ভেতরের যুক্তি

লুকানো logic সেই Dijkstra safety theorem: min-heap থেকে যে node সবচেয়ে কম known cost নিয়ে প্রথম pop হয়, সেই cost-ই তার final shortest distance (weights non-negative)। কারণ অন্য কোনো undiscovered route তাকে সস্তায় দিতে হলে অন্য frontier দিয়ে আসতে হতো, কিন্তু বাকি সব frontier-এর cost ≥ এই pop, আর edge শুধু যোগ করে। CP-তে একটা বাড়তি সূক্ষ্মতা: distance বড় হতে পারে, তাই INF যথেষ্ট বড় নিতে হয় (Python-এ float('inf') বা একটা বড় int) যাতে overflow/wrap না হয়।

কী দিয়ে তথ্য রাখব

  • adjacency list — m বড়, তাই adj[a] = [(b, w), ...]।
  • min-heap (heapq) — (cost, node); সবচেয়ে সস্তা frontier আগে।
  • dist array — প্রতিটা city-র best-known distance, শুরুতে INF, dist[1]=0।
  • lazy-skip — pop-এ cost > dist[node] হলে stale, skip (আলাদা done set না রেখেও চলে)।

এটি কেন উপযুক্ত

min-heap fit করে কারণ Dijkstra-র greedy core "cheapest frontier আগে", যা heap O(log n)-এ দেয় (../../08-heap-priority-queue/)। adjacency list fit করে কারণ CP-তে m বড়, matrix হলে O(n^2) memory ফাটে; list-এ O((V+E) log V)। dist array (INF init) fit করে কারণ CP-তে node 1-indexed আর সব city-র জন্য একটা সরাসরি slot লাগে; INF মানে "এখনো পৌঁছাইনি"। lazy-skip fit করে কারণ একই node-এ heap-এ multiple stale entry জমে; cost > dist[node] দেখে বাতিল করলে আলাদা set ছাড়াই কাজ চলে আর heap re-expansion এড়ানো যায় — বড় input-এ এটাই TLE বাঁচায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: source থেকে প্রতিটা city-তে পৌঁছানোর সব সম্ভাব্য path খুঁজে প্রতিটার মোট খরচ হিসাব করা, প্রতিটা city-র জন্য minimum রাখা।

উদাহরণ
1) city 1 থেকে প্রতিটা city-তে সব path খোঁজো (DFS/recursion)
2) প্রতিটা path-এর মোট weight যোগ করো
3) প্রতিটা city-র সবচেয়ে কম total রাখো

কোথায় বেশি কাজ হচ্ছে

সব path ঘোরা exponential — graph-এ path সংখ্যা বিস্ফোরকভাবে বাড়ে, একই subpath বারবার গোনা হয়; CP-scale 10^5 node-এ অসম্ভব। Plain BFS-ও খাটে না, কারণ weighted graph-এ "প্রথম পৌঁছানো" মানে "সবচেয়ে সস্তা" নয়। Dijkstra heap দিয়ে প্রতিটা node একবার final করে, প্রতিটা edge একবার relax — O((V+E) log V), 10^5/2·10^5-এ time limit-এর ভেতর। greedy ordering-ই exponential search এড়ায়, আর lazy-skip বাড়তি কাজ ছাঁটে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: heap-এ সবচেয়ে কম cost নিয়ে pop হওয়া node-এর distance তখনই final। তাই improve-এর জন্য পুরোনো entry মুছতে যাই না — নতুন সস্তা entry push করি, আর পুরোনো (stale) entry এলে cost > dist[node] দেখে skip করি। CP-তে এই skip শুধু সঠিকতা নয়, গতি-র জন্যও জরুরি — নাহলে heap ফুলে TLE।

আরও কম কাজে সমাধান

dist সব INF, dist[1]=0, heap = [(0, 1)]। বারবার: (cost, node) pop; cost > dist[node] হলে skip (stale); নাহলে প্রতিটা edge (v, w)-এ nd = cost + w — nd < dist[v] হলে dist[v]=nd, (nd, v) push। heap খালি হলে dist[1..n] ছাপাও। O((V+E) log V), iterative, recursion-হীন।

ভাবনার পরিবর্তন

মোচড়: "BFS দিয়ে সবার কাছে পৌঁছাই" না ভেবে ভাবো "queue → heap; cheapest-known node আগে চূড়ান্ত করি।" CP-তে এক ধাপ যোগ: lazy-skip বাধ্যতামূলক, আর distance বড় হতে পারে বলে INF যথেষ্ট বড় নাও। weights ঢুকলে FIFO ন্যায়বিচার ভাঙে — "who's next?" min-heap-এর হাতে দাও, পুরোনো হিসাব বাদ দাও।

ছবিতে বোঝা

n=4, roads (1,2,5),(1,3,2),(3,2,1),(2,4,3),(3,4,7), source 1:

উদাহরণ
        (5)
    1 -------- 2
    |         /|
 (2)|     (1) |(3)
    |   /     |
    3 ------- (to 4: 3->4 =7)
              4

heap=[(0,1)]
pop (0,1): dist[1]=0. push (5,2)(2,3).            heap: (2,3)(5,2)
pop (2,3): dist[3]=2. push (2+1=3,2)(2+7=9,4).    heap: (3,2)(5,2)(9,4)
pop (3,2): dist[2]=3 <- 1->3->2 (3) beat 1->2 (5)!
           push (3+3=6,4).                          heap: (5,2)(6,4)(9,4)
pop (5,2): cost 5 > dist[2]=3 -> stale, skip.
pop (6,4): dist[4]=6.
pop (9,4): 9 > dist[4]=6 -> stale, skip.
output: 0 3 2 6

ছোট input-এ ধাপে ধাপে

n=3, roads (1,2,4),(1,3,1),(3,2,1), source 1:

  1. dist=[INF,0,INF,INF] (1-indexed), heap [(0,1)]। pop (0,1): 0 == dist[1] ✓। edges: (2,4) → dist[2]=4, push (4,2); (3,1) → dist[3]=1, push (1,3)। heap [(1,3),(4,2)]।
  2. pop (1,3): 1 == dist[3] ✓। edge (2,1): nd=1+1=2 < dist[2]=4 → dist[2]=2, push (2,2)। heap [(2,2),(4,2)]।
  3. pop (2,2): 2 == dist[2] ✓ (final, 1→3→2 = 2 হারাল 1→2 = 4)। 2-এর edge নেই।
  4. pop (4,2): 4 > dist[2]=2 → stale, skip। heap খালি। output dist[1..3] = [0, 2, 1]।

কোড ও ব্যাখ্যা

Python

Python
import heapq


def shortest_routes(n, roads, source=1):
    INF = float("inf")
    adj = [[] for _ in range(n + 1)]      # 1-indexed
    for a, b, w in roads:                 # directed edge a -> b, weight w
        adj[a].append((b, w))

    dist = [INF] * (n + 1)
    dist[source] = 0
    heap = [(0, source)]                  # (cost so far, node)
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue                      # stale entry -> skip (lazy deletion, CP-তে জরুরি)
        for nxt, w in adj[node]:
            nd = cost + w
            if nd < dist[nxt]:            # better route found -> relax
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))

    return dist[1:n + 1]                  # city 1..n


# ---- tests ----
r1 = [(1, 2, 5), (1, 3, 2), (3, 2, 1), (2, 4, 3), (3, 4, 7)]
assert shortest_routes(4, r1, 1) == [0, 3, 2, 6]      # 1->3->2->4 = 6

assert shortest_routes(2, [(1, 2, 7)], 1) == [0, 7]
assert shortest_routes(1, [], 1) == [0]               # একা node

# 1->3->2 (2) সরাসরি 1->2 (4)-কে হারায়
assert shortest_routes(3, [(1, 2, 4), (1, 3, 1), (3, 2, 1)], 1) == [0, 2, 1]

# parallel edges: সস্তাটা জেতে
assert shortest_routes(2, [(1, 2, 9), (1, 2, 3)], 1) == [0, 3]

# unreachable city INF থাকে (এই problem-এ সাধারণত সব reachable, কিন্তু আচরণ যাচাই)
res = shortest_routes(3, [(1, 2, 5)], 1)
assert res[0] == 0 and res[1] == 5 and res[2] == float("inf")

# CP-scale sanity: লম্বা chain, recursion ছাড়াই
chain = [(i, i + 1, 1) for i in range(1, 2000)]
big = shortest_routes(2000, chain, 1)
assert big[0] == 0 and big[-1] == 1999
print("সব test pass!")

কোডের প্রতিটি অংশ

  • INF = float("inf") — "এখনো পৌঁছাইনি"; CP-তে যথেষ্ট বড়, overflow হয় না।
  • adj = [[] for _ in range(n + 1)] — 1-indexed adjacency list; index 0 ফাঁকা।
  • heap = [(0, source)] — source থেকে cost 0; tuple-এ cost আগে, যাতে heap cost দিয়ে sort করে।
  • if cost > dist[node]: continue — pop-করা cost বর্তমান best-এর চেয়ে বড় মানে stale, skip (lazy deletion)।
  • if nd < dist[nxt]: — সস্তা route পেলে dist[nxt] update আর নতুন entry push (relax)।
  • return dist[1:n + 1] — city 1..n-এর shortest distance।

Output মিলিয়ে দেখা

shortest_routes(4, r1, 1): heap সবচেয়ে সস্তা frontier ছাড়তে ছাড়তে dist[1]=0, [3]=2, [2]=3 (1→3→2 হারায় 1→2), [4]=6 (1→3→2→4); stale entry গুলো cost > dist[node]-এ skip → [0,3,2,6]। single edge → [0,7]। একা node → [0]। (1,2,4),(1,3,1),(3,2,1)-এ 1→3→2 (2) হারায় 1→2 (4) → [0,2,1]। parallel edge-এ সস্তা 3 জেতে। unreachable city INF থাকে। 2000-chain recursion ছাড়াই (heap iterative) সমাধান — CP sanity। সব assert pass, শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O((V + E) log V) — V = n, E = m। প্রতিটা edge সর্বোচ্চ একবার push, প্রতিটা push/pop একটা log V। CP-scale 10^5/2·10^5-এ আরামদায়ক।

অতিরিক্ত জায়গা

O(V + E) — adjacency list O(V + E), dist array O(V), heap worst case O(E) (lazy entry সহ)। এটাই CP-scale-এর সঠিক বাজেট।

যে ভুলগুলো এড়াতে হবে

  • lazy-skip (if cost > dist[node]: continue) বাদ দেওয়া — correctness টিকলেও heap ফুলে CP-তে TLE; এখানে এটা optional নয়।
  • (cost, node)-এর বদলে (node, cost) push করা — heap node id দিয়ে sort করে, ভুল ফল।
  • 1-indexed cities-এ array size n দেওয়া (n + 1 দরকার) — off-by-one/IndexError।
  • INF খুব ছোট নেওয়া — relax-এ cost + w যদি INF ছাড়িয়ে যায় বা wrap করে, ভুল distance (Python-এ float('inf') নিরাপদ)।
  • push-এর সময় node final mark করা — final cost শুধু প্রথম valid pop-এ, push-এ নয়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: #18 Network Delay Time (018-network-delay-time.md) আর Dijkstra theory (../shortest-path.md, ../../08-heap-priority-queue/)। হুবহু একই Dijkstra template, কিন্তু CP-নির্দিষ্ট জোর: (১) scale বড়, তাই lazy-skip বাধ্যতামূলক ও adjacency list; (২) 1-indexed I/O, INF init, সব city-র distance ছাপানো। মূল শিক্ষা একই — cheapest pop = final distance — কিন্তু এখানে শিখি কীভাবে এটা বড় input-এ TLE ছাড়া চালাতে হয়। পরের ধাপ: grid-এ Dijkstra-র minimax variant — #20।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Dijkstra (CP scale): বড় non-negative weighted graph-এ এক source থেকে সব node-এর shortest distance — min-heap-এ (cost, node), cheapest pop (distance final), edges relax করে push, আর cost > dist[node] হলে skip (lazy deletion)। CP-তে lazy-skip বাধ্যতামূলক (নাহলে TLE), INF যথেষ্ট বড় নাও, 1-indexing সামলাও। খরচ O((V+E) log V)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Shortest Routes I = Dijkstra, CP scale; min-heap-এ cheapest আগে, প্রথম pop = final, cost > dist[node] হলে skip (এখানে বাধ্যতামূলক); INF বড় নাও, 1-indexed।" যখনই 'বড় weighted graph-এ এক source থেকে সব shortest distance' দেখবে — heap-Dijkstra চালাও, lazy-skip রাখো, INF ও indexing যাচাই করো, আর negative weight হলে Bellman-Ford ভাবো।

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