Dijkstra Shortest Path

Compute the shortest path distance from a source node to all others using Dijkstra's algorithm.

dijkstra graph heap shortest-path

You are given a weighted directed graph with `n` nodes labeled from `0` to `n-1`. The graph is represented as an adjacency list: `edges = [[from, to, weight], ...]`, where `weight` is a non-negative integer. Write a function `dijkstra(n, edges, src)` that returns a list `dist` of length `n` where `dist[i]` is the shortest distance from `src` to node `i`. If node `i` is unreachable, set `dist[i] = -1`.

Constraints

- 1 <= n <= 1000
- 0 <= len(edges) <= 10^4
- Each edge weight is an integer with 0 <= weight <= 1000
- src is a valid node index (0 <= src < n)
- The graph may contain parallel edges with different weights, but no self-loops.
- The solution must run in O((V+E) log V) time using a priority queue.

Example

>>> dijkstra(3, [[0,1,2],[1,2,3]], 0)
[0, 2, 5]
>>> dijkstra(4, [[0,1,1],[1,2,2],[2,3,1]], 1)
[-1, 0, 2, 3]
>>> dijkstra(3, [[0,2,10]], 0)
[0, -1, 10]

35 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Initialize a distance array with a large number (e.g., float('inf')) and set dist[src]=0.

Use a priority queue (heapq) to repeatedly pick the unvisited node with the smallest tentative distance.

For each neighbor, relax the edge: if new distance is smaller, update and push onto the heap.

At the end, convert infinity distances to -1 in the result list.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.