DSAÝ tưởng: Từ đỉnh nguồn, luôn mở rộng đỉnh có khoảng cách nhỏ nhất chưa chốt. Dùng min-heap (priority queue) để mỗi lần lấy ra đỉnh gần nhất trong O(log V), thay vì quét tuyến tính O(V).
Vì sao không có cạnh âm: Dijkstra giả định khi một đỉnh được pop ra khỏi heap thì khoảng cách của nó đã tối ưu, vĩnh viễn không nhỏ hơn được nữa. Cạnh âm phá vỡ giả định đó (một đường vòng có thể rẻ hơn về sau) → dùng Bellman-Ford.
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
}Độ phức tạp: O(E log V) với binary heap; bộ nhớ O(V+E).
Lưu ý: Bỏ qua entry cũ bằng if (d > dist[u]) continue để khỏi xử lý lại — đây là điểm hay quên gây TLE.
Idea: From the source, always expand the unfinalized vertex with the smallest distance. Use a min-heap (priority queue) to extract the nearest vertex in O(log V) instead of a linear O(V) scan.
Why no negative edges: Dijkstra assumes that once a vertex is popped from the heap, its distance is optimal and can never get smaller. Negative edges break that assumption (a detour can become cheaper later) → use Bellman-Ford.
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]] // [distance, vertex]
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]) // real code uses a 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
}Complexity: O(E log V) with a binary heap; space O(V+E).
Note: Skip stale entries with if (d > dist[u]) continue to avoid reprocessing — a commonly forgotten step that causes TLE.