Dijkstra Shortest Path Implementation | Dataford Interview Questions

DeepMind research tooling may represent navigation or dependency relationships as weighted directed graphs. Given such a graph, implement Dijkstra's algorithm to return the shortest path from a source node to a target node.

The graph contains n nodes labeled 0 through n - 1. Each edge is represented as [u, v, weight], meaning travel from u to v costs weight. Return the node sequence for a minimum-cost path, including both endpoints. If the target is unreachable, return an empty list. If source == target, return [source]. You may assume all edge weights are nonnegative. If multiple shortest paths exist, return any one of them.

Formal Specification

Input: integers n, edges, source, and target, where edges is a list of integer triples. Output: a list of node integers describing one shortest path, or [] when no path exists.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
0 <= u, v < n for every edge [u, v, weight]
0 <= weight <= 10^9
Parallel edges and self-loops may occur
The graph is directed

Function Signature

def shortest_path(n, edges, source, target):

Your question is Dijkstra Shortest Path Implementation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem