Dijkstra and Shortest Paths
Decide between Dijkstra, Bellman-Ford, and 0/1 BFS, and trace Dijkstra on a small weighted graph. Code stems are Python.
Question Bank
Hard
Python
dijkstra
shortest-path
bellman-ford
algorithms
952 views
18
Implement Dijkstra's algorithm with a min-heap. Return a distance array from src over n vertices given a list of (u, v, w) edges (directed).
Examples
Example 1:
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]
Explanation: Pop 0 (d = 0), relax B = 4, C = 1. Pop C (d = 1), relax B = min(4, 1 + 2) = 3, D = 1 + 5 = 6. Pop B (d = 3), relax D = min(6, 3 + 1) = 4. Pop D (d = 4). Each finalize is O(log V) via the min-heap.4 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium