কনটেন্টে যান

018 — Network Delay Time

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

Problem link ও উৎস

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

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

n টা node (1 থেকে n) আর একটা signal-নেটওয়ার্ক আছে। times-এ প্রতিটা entry (u, v, w) মানে "node u থেকে node v-তে signal যেতে w সময় লাগে" (directed edge, weight w)। তুমি node k থেকে একটা signal ছাড়ো। বলো: সব node-এ signal পৌঁছাতে মোট কত সময় লাগবে — অর্থাৎ k থেকে সবচেয়ে দূরের node-এর shortest-path দূরত্ব। কোনো node-এ পৌঁছানো না গেলে -1।

উদাহরণ
k থেকে প্রতিটা node-এর shortest time বের করো
উত্তর = max(সব shortest time)   (কারণ signal সবার কাছে পৌঁছাতে এতটাই লাগে)
কেউ unreachable হলে -> -1

Input ও output

উদাহরণ
Input : n=4, times=[(1,2,1),(1,3,4),(2,3,1),(3,4,2)], k=1
Output: 4        (সবচেয়ে দূরের node 4-এ পৌঁছাতে 4)

Input : n=2, times=[(1,2,1)], k=1
Output: 1        (একটাই edge)

Edge case (unreachable): n=2, times=[(1,2,1)], k=2 -> -1  (2 থেকে 1-এ যাওয়া যায় না)

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

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

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

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

মূল ভিত হলো heap / priority queue (../../08-heap-priority-queue/) আর BFS (../bfs.md), যা মিলে Dijkstra বানায় (../shortest-path.md)। shortest-path.md-এর মূল সূত্র: Dijkstra = BFS + greedy choice + priority queue। BFS unweighted-এ কাজ করে কারণ queue ঘটনাক্রমে nodes-কে distance-order-এ ছাড়ে; weights যোগ হলে সেই ভাগ্য মরে যায়, তাই FIFO queue-র বদলে cost-এ key করা min-heap বসাই — পরে যে node ছাড়ি সে "সবচেয়ে কম known total cost"-এর node।

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

লুকানো logic Dijkstra-র safety theorem: যখন একটা node সবচেয়ে কম known cost নিয়ে heap থেকে pop হয়, সেই cost-ই তার final shortest distance। কেন? অন্য কোনো undiscovered route তাকে সস্তায় দিতে হলে অন্য কোনো frontier node দিয়ে আসতে হতো, কিন্তু বাকি সব frontier-এর cost এখন ≥ এই pop-করা cost, আর extra edge শুধু যোগ করে (weights non-negative)। তাই "cheapest so far" = "cheapest forever"। প্রতিটা node-এর final distance বের করে তাদের maximum-ই উত্তর (signal শেষ node-এ পৌঁছাতে এতটাই লাগে)।

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

  • adjacency list — times থেকে adj[u] = [(v, w), ...]।
  • min-heap (heapq) — (cost, node); সবসময় সবচেয়ে সস্তা frontier আগে দেয়।
  • dist dict/array — প্রতিটা node-এর best-known cost।
  • done set (বা dist-এর সাথে lazy-skip) — যেসব node-এর distance final।

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

min-heap fit করে কারণ Dijkstra-র greedy move-টাই "সবচেয়ে সস্তা frontier আগে process করো", আর heap ঠিক সেটা O(log n)-এ দেয় (../../08-heap-priority-queue/)। adjacency list fit করে কারণ প্রতিটা node থেকে শুধু তার outgoing edges relax করতে হয় — O((V+E) log V)। dist + done (বা lazy-skip) fit করে কারণ একই node-এ heap-এ একাধিক stale entry থাকতে পারে; final হয়ে যাওয়া node আবার pop হলে skip করি — আলাদা করে heap থেকে মুছি না (lazy deletion)।

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

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

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

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

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

সব path ঘুরে দেখা exponential — একটা graph-এ path সংখ্যা node-সংখ্যার সাথে বিস্ফোরকভাবে বাড়ে, একই subpath বারবার হিসাব হয়। Plain BFS এখানে কাজ করে না, কারণ weighted graph-এ "প্রথম পৌঁছানো" মানে "সবচেয়ে সস্তা" নয় (cost-3-এর 2-edge route, cost-10-এর 1-edge route-কে হারাতে পারে)। Dijkstra heap দিয়ে এই সমস্যা মেটায়: প্রতিটা node ঠিক একবার final হয়, প্রতিটা edge একবার relax — O((V+E) log V)। greedy ordering-ই exponential search এড়ায়।

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

মূল observation: heap থেকে যে node সবচেয়ে কম cost নিয়ে pop হয়, তার distance তখনই final (non-negative weights-এ)। তাই কোনো node-কে দ্বিতীয়বার "improve" করার দরকার নেই — পুরোনো stale entry এলে শুধু skip করি। সব node final হলে তাদের max-ই signal-এর মোট সময়।

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

dist খালি, heap = [(0, k)]। বারবার: সবচেয়ে সস্তা (cost, node) pop করো; node আগেই done হলে skip (lazy); নাহলে final mark করো, তার প্রতিটা edge (v, w)-এ new = cost + w — যদি v-র জানা cost-এর চেয়ে কম, dist[v] update করে (new, v) push। heap খালি হলে: সব node reach হয়েছে কিনা দেখো; হলে max(dist.values()), নাহলে -1। O((V+E) log V)।

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

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

ছবিতে বোঝা

n=4, edges (1,2,1),(1,3,4),(2,3,1),(3,4,2), source k=1:

উদাহরণ
        (1)
    1 -------- 2
    |         /
 (4)|     (1)
    |   /
    3 -------- 4
        (2)

heap=[(0,1)]
pop (0,1): final dist[1]=0. push (1,2)(4,3).        heap: (1,2)(4,3)
pop (1,2): final dist[2]=1. push (1+1=2,3).         heap: (2,3)(4,3)
pop (2,3): final dist[3]=2 <- 1->2->3 (2) beat 1->3 (4)!
           push (2+2=4,4).                           heap: (4,3)(4,4)
pop (4,3): 3 already final -> stale, skip.
pop (4,4): final dist[4]=4.
উত্তর = max(0,1,2,4) = 4

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

n=3, edges (1,2,2),(1,3,5),(2,3,1), k=1:

  1. dist={}, heap [(0,1)]। pop (0,1): done নয় → dist[1]=0। edges: (2,2) → dist[2]=2, push (2,2); (3,5) → dist[3]=5, push (3,3)। heap [(2,2),(3,3)... (5,3)] → আসলে [(2,2),(5,3)]।
  2. pop (2,2): → dist[2]=2 final। edge (3,1): new=2+1=3 < 5 → dist[3]=3, push (3,3)। heap [(3,3),(5,3)]।
  3. pop (3,3): → dist[3]=3 final (1→2→3 = 3, 1→3 = 5-কে হারাল)। 3-এর edge নেই।
  4. pop (5,3): 3 আগেই final → stale, skip। heap খালি। সব node reach (dist size 3 = n)। উত্তর = max(0,2,3) = 3।

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

Python

Python
import heapq
from collections import defaultdict


def network_delay_time(n, times, k):
    adj = defaultdict(list)
    for u, v, w in times:                 # directed edge u -> v, weight w
        adj[u].append((v, w))

    dist = {}                             # node -> final shortest cost
    heap = [(0, k)]                       # (cost so far, node)
    while heap:
        cost, node = heapq.heappop(heap)  # সবচেয়ে সস্তা known route
        if node in dist:
            continue                      # stale entry -> skip (lazy deletion)
        dist[node] = cost                 # এই cost এখন প্রমাণিতভাবে final
        for nxt, w in adj[node]:
            new_cost = cost + w
            if nxt not in dist:           # final node আবার relax করার দরকার নেই
                heapq.heappush(heap, (new_cost, nxt))

    if len(dist) < n:                     # কোনো node-এ পৌঁছানো গেল না
        return -1
    return max(dist.values())             # সবার কাছে পৌঁছাতে এতটাই লাগে


# ---- tests ----
assert network_delay_time(4, [(1, 2, 1), (1, 3, 4), (2, 3, 1), (3, 4, 2)], 1) == 4
assert network_delay_time(2, [(1, 2, 1)], 1) == 1
assert network_delay_time(2, [(1, 2, 1)], 2) == -1          # 2 থেকে 1 unreachable
assert network_delay_time(3, [(1, 2, 2), (1, 3, 5), (2, 3, 1)], 1) == 3  # 1->2->3 হারায়
assert network_delay_time(1, [], 1) == 0                    # একটাই node, dist 0

# 0-weight edge ও multi-path: cheapest জেতে
assert network_delay_time(3, [(1, 2, 0), (2, 3, 0), (1, 3, 5)], 1) == 0
print("সব test pass!")

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

  • adj[u].append((v, w)) — directed weighted edge; Dijkstra-তে direction matters।
  • heap = [(0, k)] — source থেকে cost 0; tuple-এ cost আগে, যাতে heap cost দিয়ে sort করে।
  • if node in dist: continue — node আগেই final হলে এটা stale entry, skip (lazy deletion, ../../08-heap-priority-queue/)।
  • dist[node] = cost — প্রথম pop-এ এই cost প্রমাণিতভাবে final।
  • if nxt not in dist: — already-final node আবার push করার দরকার নেই; এড়িয়ে heap ছোট রাখি।
  • len(dist) < n: return -1 — কোনো node unreachable হলে; নাহলে max(dist.values()) = সবচেয়ে দূরের node।

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

network_delay_time(4, [...], 1): heap সবচেয়ে সস্তা frontier ছাড়তে ছাড়তে dist[1]=0, [2]=1, [3]=2 (1→2→3 path 1→3-কে হারায়), [4]=4; stale (4,3) skip; সব reach, max=4। single edge → 1। source 2 থেকে 1 unreachable → len(dist)=1<2 → -1। (1,2,2),(1,3,5),(2,3,1)-এ 1→2→3 (3) সরাসরি 1→3 (5)-কে হারায় → 3। একা node → 0। 0-weight path → 0। সব assert pass, শেষে print: সব test pass!।

JavaScript ও test cases

JS-এ built-in heap নেই, তাই ছোট একটা binary MinHeap লিখে Dijkstra; (cost, node) cheapest আগে, lazy-skip।

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// minimal binary min-heap of [cost, node], cost দিয়ে compare
class MinHeap {
  constructor() { this.h = []; }
  push(item) {
    const h = this.h; h.push(item); let i = h.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (h[p][0] <= h[i][0]) break; [h[p], h[i]] = [h[i], h[p]]; i = p; }
  }
  pop() {
    const h = this.h; const top = h[0], last = h.pop();
    if (h.length) { h[0] = last; let i = 0;
      for (;;) { let s = i; const l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && h[l][0] < h[s][0]) s = l;
        if (r < h.length && h[r][0] < h[s][0]) s = r;
        if (s === i) break; [h[s], h[i]] = [h[i], h[s]]; i = s; } }
    return top;
  }
  get size() { return this.h.length; }
}
// times: [u, v, w] directed edge u->v weight w; source k; node 1..n
function networkDelayTime(n, times, k) {
  const adj = new Map();
  for (const [u, v, w] of times) {
    if (!adj.has(u)) adj.set(u, []);          // shared-ref এড়িয়ে নতুন array
    adj.get(u).push([v, w]);
  }
  const dist = new Map();                     // node -> final shortest cost
  const heap = new MinHeap();
  heap.push([0, k]);
  while (heap.size) {
    const [cost, node] = heap.pop();          // cheapest known route
    if (dist.has(node)) continue;             // stale -> skip (lazy deletion)
    dist.set(node, cost);
    for (const [nxt, w] of adj.get(node) || []) {
      if (!dist.has(nxt)) heap.push([cost + w, nxt]);
    }
  }
  if (dist.size < n) return -1;               // কোনো node unreachable
  return Math.max(...dist.values());          // সবার কাছে পৌঁছাতে এতটাই লাগে
}
// ---- test cases (example + edge) ----
assert(networkDelayTime(4, [[1, 2, 1], [1, 3, 4], [2, 3, 1], [3, 4, 2]], 1) === 4, "spread");
assert(networkDelayTime(2, [[1, 2, 1]], 1) === 1, "single-edge");
assert(networkDelayTime(2, [[1, 2, 1]], 2) === -1, "unreachable");        // edge
assert(networkDelayTime(3, [[1, 2, 2], [1, 3, 5], [2, 3, 1]], 1) === 3, "2-edge beats 1");
assert(networkDelayTime(1, [], 1) === 0, "single-node");
assert(networkDelayTime(3, [[1, 2, 0], [2, 3, 0], [1, 3, 5]], 1) === 0, "zero-weight");
console.log("সব JS test pass!");

JS টীকা: JS-এ built-in priority queue নেই — তাই উপরের মতো একটা binary heap লিখতে হয় (অথবা ছোট graph-এ array linear-scan)। heap-এ tuple compare করো শুধু item[0] (cost) দিয়ে, পুরো array নয়। Math.max(...dist.values()) spread দিয়ে চলে, কিন্তু খুব বড় set-এ stack-limit ভাঙতে পারে — তখন reduce ব্যবহার করো। adjacency-তে Map.get(u) না থাকলে নতুন array set করো (shared-ref এড়াতে)।

TypeScript ও test cases

TypeScript
type Item = [number, number];   // [cost, node]
class MinHeap {
  private h: Item[] = [];
  push(item: Item): void {
    const h = this.h; h.push(item); let i = h.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (h[p][0] <= h[i][0]) break; [h[p], h[i]] = [h[i], h[p]]; i = p; }
  }
  pop(): Item {
    const h = this.h; const top = h[0], last = h.pop() as Item;
    if (h.length) { h[0] = last; let i = 0;
      for (;;) { let s = i; const l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && h[l][0] < h[s][0]) s = l;
        if (r < h.length && h[r][0] < h[s][0]) s = r;
        if (s === i) break; [h[s], h[i]] = [h[i], h[s]]; i = s; } }
    return top;
  }
  get size(): number { return this.h.length; }
}
function networkDelayTime(n: number, times: number[][], k: number): number {
  const adj: Map<number, Item[]> = new Map();
  for (const [u, v, w] of times) {
    if (!adj.has(u)) adj.set(u, []);
    (adj.get(u) as Item[]).push([v, w]);
  }
  const dist: Map<number, number> = new Map();
  const heap = new MinHeap();
  heap.push([0, k]);
  while (heap.size) {
    const [cost, node] = heap.pop();
    if (dist.has(node)) continue;
    dist.set(node, cost);
    for (const [nxt, w] of adj.get(node) ?? []) {
      if (!dist.has(nxt)) heap.push([cost + w, nxt]);
    }
  }
  if (dist.size < n) return -1;
  return Math.max(...dist.values());
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(networkDelayTime(4, [[1, 2, 1], [1, 3, 4], [2, 3, 1], [3, 4, 2]], 1), 4, "spread");
expect(networkDelayTime(2, [[1, 2, 1]], 2), -1, "unreachable");
expect(networkDelayTime(3, [[1, 2, 2], [1, 3, 5], [2, 3, 1]], 1), 3, "beats");
console.log("সব TS test pass!");

TS টীকা: type Item = [number, number] দিয়ে heap-এর element-কে নাম দিলে heap class ও Dijkstra দুজায়গাতেই [cost, node] আকৃতি locked থাকে; Map<number, number> (dist) ও Map<number, Item[]> (adj) typing করায় ভুল key/value নীরবে ঢোকে না। private h: Item[] দিয়ে heap-এর ভেতরের array encapsulated।

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

সময়

O((V + E) log V) — প্রতিটা edge সর্বোচ্চ একবার push হতে পারে, প্রতিটা push/pop একটা log V; heap-ভিত্তিক Dijkstra-র আদর্শ খরচ।

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

O(V + E) — adjacency list O(V + E), dist dict O(V), heap worst case O(E) (lazy entry সহ)।

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

  • negative weight থাকলে Dijkstra চালানো — এটা নীরবে ভুল উত্তর দেয় (greedy stamp ভেঙে যায়); negative হলে Bellman-Ford (../shortest-path.md)।
  • (cost, node)-এর বদলে (node, cost) push করা — heap তখন node id দিয়ে sort করে, ভুল ফল।
  • if node in dist: continue (lazy-skip) বাদ দেওয়া — correctness প্রায়ই টেকে, কিন্তু stale entry পুরো re-expand হয়, ধীর।
  • push-এর সময় node final mark করা — Dijkstra-তে node-এর final cost শুধু প্রথম pop-এ, প্রথম push-এ নয়।
  • শেষে সব node reach হয়েছে কিনা না দেখে max নেওয়া — unreachable থাকলে -1 ফেরত দিতে হয়।

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

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

ভিত্তি: heap (../../08-heap-priority-queue/) আর BFS (../bfs.md), যা মিলে Dijkstra (../shortest-path.md)। এটা tracker-এর প্রথম weighted shortest-path problem — এখানে শেখা হয় কীভাবে BFS-এর FIFO queue-কে min-heap দিয়ে বদলে weights সামলাতে হয়, আর "প্রথম pop = final distance" theorem-টা কেন খাটে। মূল নতুন শিক্ষা: lazy deletion সহ Dijkstra-র template, যা পরবর্তী সব shortest-path variant-এর ভিত্তি। পরের ধাপ: একই Dijkstra CP scale-এ — #19।

পরের অনুশীলন

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

Dijkstra (single-source shortest paths): non-negative weighted graph-এ এক source থেকে সব node-এর shortest distance — min-heap-এ (cost, node) রাখো, সবচেয়ে সস্তা pop করো (তার distance তখনই final), edges relax করে improved entry push করো, stale entry skip (lazy deletion)। খরচ O((V+E) log V)। "সবার কাছে পৌঁছানো" = distance-গুলোর max।

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

ভবিষ্যতের আমাকে: "Network Delay = Dijkstra; min-heap-এ cheapest আগে, প্রথম pop = final distance, stale skip; উত্তর = max(সব dist), unreachable থাকলে -1।" যখনই 'weighted graph-এ এক source থেকে cheapest/fastest distance' দেখবে — BFS-এর queue-কে heap দিয়ে বদলাও, (cost, node) order মনে রাখো, lazy-skip রাখো, আর negative weight হলে Dijkstra বাদ দিয়ে Bellman-Ford ভাবো।

কোথায় কাজে লাগে

  • Network routing: router-এ shortest/fastest path বের করা (OSPF-ধাঁচের link-state routing Dijkstra-ভিত্তিক)।
  • Maps / navigation: road network-এ A থেকে সব গন্তব্যে দ্রুততম সময়/দূরত্ব; weight = travel time।
  • Signal / broadcast latency: এক source থেকে সব node-এ সংকেত পৌঁছাতে মোট সময় (literally এই problem)।
  • Game pathfinding: weighted grid/graph-এ unit-এর সবচেয়ে সস্তা পথ (Dijkstra বা তার heuristic-বর্ধিত রূপ A*)।
  • Telecom / utility planning: সবচেয়ে কম খরচে সব station-এ পরিষেবা পৌঁছানোর cost estimate।

মূল pattern: non-negative weighted graph-এ এক source থেকে cheapest/fastest distance = min-heap Dijkstra; "সবার কাছে পৌঁছানো" = distance-গুলোর max।

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