Dijkstra tìm đường ngắn nhất (ví dụ Network Delay Time) — vì sao cần min-heap và sao Dijkstra không chạy được với cạnh âm?

function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => [])
  for (const [u, v, w] of times) adj[u].push([v, w])
  const dist = new Array(n + 1).fill(Infinity)
  dist[k] = 0
  const heap: [number, number][] = [[0, k]] // [khoảng cách, đỉnh]
  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]) // thực tế dùng binary heap
    const [d, u] = heap.shift()!
    if (d > dist[u]) continue
    for (const [v, w] of adj[u])
      if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]) }
  }
  const ans = Math.max(...dist.slice(1))
  return ans === Infinity ? -1 : ans
}