Reference no: EM132399159

This is a Max Flow problem. Any help would be greatly appreciated.

A number k of trucking companies, c1, . . . , ck, want to use a common road system, which is modeled as a directed graph, for delivering goods from source locations to a common target location. Each trucking company ci has its own source location, modeled as a vertex si in the graph, and the common target location is another vertex t. (All these k + 1 vertices are distinct.) The trucking companies want to share the road system for delivering their goods, but they want to avoid getting in each other's way while driving. Thus, they want to find k edge-disjoint paths in the graph, one connecting each source si to the target t. We assume that there is no problem if trucks of different companies pass through a common vertex. Design an algorithm for the companies to use to determine k such paths, if possible, and otherwise return "impossible".