Dijkstra's shortest paths
Problem
Given a weighted graph with non-negative edge weights and a source node, return the shortest distance from the source to every node. Network Delay Time asks for the largest of those distances, or −1 if some node is unreachable.
Example 1
Input: edges (u, v, w) = [[2,1,1], [2,3,1], [3,4,1]], n = 4, source = 2 Output: distances 1:1, 2:0, 3:1, 4:2 → network delay 2
Also asked as: Dijkstra algo
Test cases
Case 1
Input: [[[1,4],[2,1]],[[3,1]],[[1,2],[3,5]],[]], 0 Expected: [0,3,1,4]
Case 2
Input: [[[1,7]],[[0,7]]], 1 Expected: [7,0]
Case 3
Input: [[]], 0 Expected: [0]
View solutionHide solution1 approach
1. Min-priority queue by tentative distance
Time O((V + E) log V)Space O(V)
Repeatedly pop the closest unfinalised node and relax its edges. Needs non-negative weights.
function dijkstra(adj, src) { // adj[u] = [[v, w], ...] const dist = new Array(adj.length).fill(Infinity); dist[src] = 0; const pq = [[0, src]]; // [d, node]; simple array used as a min-heap while (pq.length) { pq.sort((a, b) => a[0] - b[0]); const [d, u] = pq.shift(); if (d > dist[u]) continue; for (const [v, w] of adj[u]) { if (d + w < dist[v]) { dist[v] = d + w; pq.push([dist[v], v]); } } } return dist;}