Dijkstra's Algorithm

Given a weighted, directed graph with **n** vertices (non-negative edge weights) and a source vertex, return the **shortest distance** from the source to every other vertex using **Dijkstra's algorithm**. Unreachable vertices should have distance **Infinity**.

Examples

Input: n = 4, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], src = 0

Output: [0,3,1,4]

Shortest path to 1 is via 2 (1+2=3); to 3 is via 2→1 (1+2+1=4).

Constraints

• 1 <= n <= 2000
• Edge weights are non-negative
• edges[i] = [u, v, weight] meaning a directed edge u → v

Complexity Analysis

Time

O((V + E) log V) using a min-priority queue (binary heap).

Space

O(V + E) for the adjacency list and distance array.

Test Cases

#1 — Classic Dijkstra example

Input: n=4 edges=[[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]] src=0

Expected: [0,3,1,4]

#2 — Unreachable vertex returns Infinity (serialized as null in JSON)

Input: n=2 edges=[] src=0

Expected: [0,null]

#3 — Simple chain

Input: n=3 edges=[[0,1,1],[1,2,1]] src=0

Expected: [0,1,2]

Step-by-step visualizer available!

Switch to the Visualize ✨ tab to watch this algorithm run step-by-step on a live graph before you code.