Min-Cost Flow Successive Shortest Path One Step

Problem

Perform one successive-shortest-path augmentation for min-cost flow from s to t.

Starting from zero flow, run Dijkstra on positive residual capacities using the edge costs, recording parents. Return [path, bottleneck, path_cost] where path is the node list from s to t, bottleneck is the smallest residual capacity along it, and path_cost is the total cost; return [[], 0, 0] when no path exists. edges is a list of [u, v, capacity, cost] tuples with non-negative costs.

Hint

Successive shortest paths with residual reverse edges solve min-cost flow exactly.

Test cases

case 1

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

expected: [[0,1,2],2,4]

case 2

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

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

case 3

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

expected: [[],0,0]

Starter codePython

import heapq
def min_cost_flow_step(n, edges, s, t):
    # Your code here
    pass

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