Minimize number of edges used when making multiple routes

Question

The title maybe isn't clear, but I'll try to explain better here:

• Suppose we have a directed weighted graph G, with N nodes and K edges.
• There is two main nodes: Node 1 and Node N. Our main goal is to go from 1 to N. And usually there is multiple possible paths from 1 to N.
• We also have M people that want to travel from 1 to N.
• Every edge has a weight w. The weight means how many people simultaneously can pass through that edge.
• Every edge can be imagined as a road, that takes 1 day to pass.

What we want to do is to make the M people go to node N, from node 1, minimizing the number of days.

For example:

example of graph

In this graph, if we have 3 people to pass, the minimum number of days is 2. We pass 2 people to the node 2 and 1 person to node 3. The 2 people will take 2 days to go to node 3, and 1 person will take 1 day to go to node 3.

My question is: How to solve this? Is it with max-flow? If yes, how to model the problem so that it can be solved with max-flow?

Answer 1

• Apply max-flow algorithm in normal way
• If max-flow result is less than M
  • no solution
• If max-flow result is equal to M
  • solved
• If max-flow result is greater than M
  • remove people from max max flow result in order of longest trip until M left.