CODEWITHSUNDEEP
algorithmgraph-theorypath-finding
Qiaolun
Qiaolun

Reputation: 21

Soving widest path problem with node capacity constraints

Suppose that I have a graph and a set of requests between node pairs. For each request, I need to find a path with maximum capacity (the maximum of the minimum capacity of the links in the path). Besides, each node has a capacity and the nodes in the path consume the node capacity. I want to serve as many requests as possible (maximizing the request of it).

In summary, it's a widest path problem with node capacity constraints. How can I solve it?

Upvotes: 1

Views: 101

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

Split each node into two, connected by a link with capacity equal to original node capacity. One node is the destination for all the in links, the other is the source for all the out links. Apply usual algorithm.

Upvotes: 2

Related Questions