Shortest Distance from Source (Dijkstra's Algorithm)

Given a weighted directed graph represented as an adjacency list graph and a source node src, return an array dist where dist[i] represents the shortest distance (sum of edge weights) from src to node i. If node i is unreachable from src, dist[i] should be Infinity. The distance from src to itself is 0.

Note:

• The graph representation uses [neighbor, weight] pairs for each edge, where weight is a non-negative number.

Examples

Input: graph = [[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], src = 0
Output: [0, 3, 1, 4]
Explanation:
- Distance from 0 to 0: 0 (same node)
- Distance from 0 to 1: 3 (0 -> 2 -> 1, weight: 1 + 2 = 3, not 0 -> 1 with weight 4)
- Distance from 0 to 2: 1 (direct edge with weight 1)
- Distance from 0 to 3: 4 (0 -> 2 -> 1 -> 3, weight: 1 + 2 + 1 = 4)

Input: graph = [[[1, 5], [2, 2]], [[3, 1]], [[1, 1], [3, 3]], []], src = 0
Output: [0, 3, 2, 4]
Explanation:
- 0 -> 2 -> 1: weight 2 + 1 = 3 (shorter than 0 -> 1 with weight 5)
- 0 -> 2 -> 3: weight 2 + 3 = 5
- 0 -> 2 -> 1 -> 3: weight 2 + 1 + 1 = 4 (shortest path to 3)

Input: graph = [[[1, 10]], []], src = 1
Output: [Infinity, 0]
Explanation: Node 1 cannot reach node 0

Constraints

• Graph is represented as an adjacency list where graph[i] contains an array of [neighbor, weight] pairs
• All edge weights are non-negative (≥ 0)
• Nodes are numbered from 0 to n-1 where n is the number of nodes
• Graph may contain cycles
• Graph may be disconnected
• Distance from src to itself is always 0
• Unreachable nodes have distance Infinity
• The algorithm requires a MinHeap/Priority Queue to efficiently select the node with minimum distance

Function Signature

function dijkstras(graph, src) {
  // Your code here
}

Test Cases

• Base cases: single node graph [[[]]], 0 -> [0]
• Direct edges: [[[1, 5]], []], 0 -> [0, 5]
• Multiple paths: [[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], 0 -> [0, 3, 1, 4]
• Disconnected nodes: [[[1, 2]], [], [[3, 1]], []], 0 -> [0, 2, Infinity, Infinity]
• Graph with cycles: [[[1, 1], [2, 3]], [[2, 1]], [[0, 2]]], 0 -> [0, 1, 2, ...]
• Source with no outgoing edges: [[], [[0, 1]], []], 1 -> [1, 0, Infinity]
• Large graphs with various edge weights