Dijkstra: Shortest Distances
Advanced
A directed graph has n nodes and weighted edges [a, b, w] (an arrow from a to b of length w >= 0). Return a list with the shortest distance from source to every node, using -1 for nodes that cannot be reached.
For n = 3, edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2]] and source = 0 the answer is [0, 3, 1].
The starter code finds the closest unfinished node by scanning all nodes every time. It is correct but too slow for a large graph.
Examples
Example 1
Input:
shortest_distances(3, [[0, 1, 4], [0, 2, 1], [2, 1, 2]], 0)
Output:
[0, 3, 1]
Example 2
Input:
shortest_distances(3, [[1, 2, 5]], 0)
Output:
[0, -1, -1]
Constraints
1 <= n <= 1000000 <= len(edges) <= 2000000 <= w <= 10**4
Theory
Go to TheoryKeywords
dsa-sheetgraphsshortest-paths-and-ordering
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.