Neural Mastery
← Practice
Dijkstra's Single-Source Shortest Pathsmedium

Dijkstra's Single-Source Shortest Paths

medium Coding Interview Patterns 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Interactive
Graph & Tree Traversal, Step by Step
Structure
Algorithm
ABCDE
visiting A -> visited order so far: [A]
queue now: [B, C]
Step 1 / 5
Both modes run the real algorithm from the linked practice problem, one step at a time -- edit the graph or pick different tree nodes and every step recomputes live.

Find shortest paths from a source to all nodes in a weighted graph using Dijkstra's algorithm.

Task

Implement dijkstra_shortest_paths(n, edges, src): use a priority queue (min-heap) to explore nodes in order of current shortest tentative distance.

Function Signature

dijkstra_shortest_paths(n: int, edges: list[list[int]], src: int) -> dict[int, int]

Examples

Example 1: 5 Nodes Weighted Graph
Input: n = 5 edges = [[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]] src = 0
Output: {'0': 0, '1': 3, '2': 2, '3': 8, '4': 10}
Example 2: Graph with Unreachable Node
Input: n = 3 edges = [[0, 1, 3]] src = 0
Output: {'0': 0, '1': 3, '2': -1}

Constraints

  • 1 <= n <= 1000
  • 0 <= len(edges) <= 10^4
  • All edge weights >= 0
Python3Saved ✓
def dijkstra_shortest_paths(n: int, edges: list[list[int]], src: int) -> dict[int, int]:
"""n: number of vertices (0 to n-1).
edges: list of [u, v, weight] undirected edges with non-negative weights.
src: source vertex.
Return dict mapping each node 0..n-1 to its shortest distance from src (use -1 if unreachable)."""
# Your implementation here
pass

Case 1: 5 Nodes Weighted Graph
Input: n = 5 edges = [[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]] src = 0
Expected: {'0': 0, '1': 3, '2': 2, '3': 8, '4': 10}
Case 2: Graph with Unreachable Node
Input: n = 3 edges = [[0, 1, 3]] src = 0
Expected: {'0': 0, '1': 3, '2': -1}