Shortest Path Dual

Problem

Check a potential vector for the shortest-path LP dual.

The dual requires d[v] <= d[u] + cost for every arc (u, v, cost). If all arcs satisfy this within tol, return [True, d[t] - d[s]]; otherwise return [False, 0.0].

Hint

Feasible potentials are exactly the distance labels of the shortest-path tree.

Test cases

case 1

in: [[[0,1,2],[1,2,3]],3,[0,2,5],0,2,1e-9]

expected: [true,5]

case 2

in: [[[0,1,2],[1,2,1]],3,[0,2,5],0,2,1e-9]

expected: [false,0]

case 3

in: [[[0,1,1]],2,[0,1],0,1,1e-9]

expected: [true,1]

Starter codePython

def shortest_path_dual(edges, n, d, s, t, tol):
    # Returns [feasible, value]
    # Your code here
    pass

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