Dijkstra Shortest Path Trace

Problem

Reconstruct one concrete shortest path in an undirected graph with positive weights.

edges is a list of [u, v, w] triples and both directions are usable. Track predecessors whenever a strict distance improvement happens, then walk backward from target to source. Return [] when target is unreachable and [source] when both nodes are equal.

Hint

Only overwrite the predecessor on a strict improvement, then backtrack from target.

Test cases

case 1

in: [5,[[0,1,2],[0,2,1],[1,3,2],[2,3,2],[3,4,1]],0,4]

expected: [0,2,3,4]

case 2

in: [3,[[0,1,1]],0,2]

expected: []

case 3

in: [3,[[0,1,5],[1,2,5]],0,0]

expected: [0]

case 4

in: [4,[[0,1,10],[0,2,1],[2,1,1],[1,3,1]],0,3]

expected: [0,2,1,3]

case 5

in: [2,[[0,1,3]],1,0]

expected: [1,0]

Starter codePython

import heapq

def dijkstra_path(n, edges, source, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor