Dijkstra's shortest paths

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}