Your question is Dijkstra Shortest Path Implementation. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
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.
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.
def shortest_path(n, edges, source, target):