Skip to content

019 — Shortest Routes I

Source

  • Original source: Classic single-source shortest-path (Dijkstra) exercise, competitive-programming scale
  • Platform: CSES Problem Set — https://cses.fi/problemset/task/1671
  • Topic: graphs
  • Difficulty: Medium
  • Pattern: Dijkstra, CP scale
  • Basic idea inherited from: Network Delay Time (018-network-delay-time.md, এই tracker-এর #18); shortest paths (../shortest-path.md); heap (../../08-heap-priority-queue/)

1. Problem in simple words

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: dist[1] dist[2] ... dist[n]
(সব city reachable ধরা হয় এই problem-এ)

2. Which basic idea does this inherit from?

মূল ভিত হলো #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।

3. What is the hidden math or logic?

লুকানো 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 না হয়।

4. Which data structure is needed?

  • 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 না রেখেও চলে)।

5. Why this data structure fits

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 বাঁচায়।

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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]

9. Brute force thinking

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

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

10. Why brute force is slow

সব 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 বাড়তি কাজ ছাঁটে।

11. Key observation

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

12. Optimized intuition

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-হীন।

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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!")

16. Line-by-line code explanation

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

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • 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-এ নয়।

21. Which basic problem this inherits from

ভিত্তি: #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।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।