DAG Shortest Path

Problem

Compute single-source shortest paths in a directed acyclic graph in linear time, even with negative edge weights.

Process nodes in topological order and relax every outgoing edge. Return distances from src in node order, using -1 for unreachable nodes. edges is a list of [u, v, w] triples. Avoid tests whose reachable distance equals -1.

Hint

Topological order means each node's distance is final before its edges are relaxed.

Test cases

case 1

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

expected: [0,2,1,4]

case 2

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

expected: [0,1,3,6]

case 3

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

expected: [0,4,-1]

Starter codePython

import heapq
def dag_shortest_path(n, edges, src):
    # Your code here
    pass

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