Shortest paths from one source through non-negative weighted edges. Always expand the closest unsettled node, its distance is final, then relax its neighbors.
Keep a tentative distance for every node. Pull the smallest one from a min-heap, its distance can't improve anymore, so lock it in. Then try to shorten its neighbors' distances (relaxation).
dist[src]=0, everything else ∞u→v: if dist[u]+w < dist[v], updateint networkDelayTime(vector<vector<int>>& times, int n, int src) {
vector<vector<pair<int,int>>> adj(n + 1);
for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
vector<int> dist(n + 1, INT_MAX);
dist[src] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>,
greater<>> pq; // min-heap: {dist, node}
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry, skip
for (auto& [v, w] : adj[u])
if (dist[u] + w < dist[v]) { // relax edge u→v
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INT_MAX) return -1; // unreachable
ans = max(ans, dist[i]);
}
return ans; // slowest arrival = network delay
}Each edge triggers at most one heap push; heap ops are log V.
Adjacency list, distance array, and the priority queue.
Fails on negative edges. Use Bellman-Ford there.
if (d > dist[u]) continue guard is the lazy-deletion trick, cheaper than decrease-key on a binary heap.O(V²) array-scan Dijkstra can beat the heap version.