最小化多个路线时使用的边缘数量
标题可能不清楚，但我会在这里尝试更好地解释：
- 假设我们有一个定向加权图G，带有N节点和K边缘。
- 有两个主要节点：节点1和NodeN。我们的主要目标是从1到N。通常有多个可能的路径从1到N。
- 也有M的人想从1到N。
- 我们 边缘具有重量w。体重意味着有多少人同时可以通过该边缘。
- 每个边缘都可以被认为是一条路，需要1天才能通过。
我们要做的是使M人从节点1进入Node N，从而最大程度地减少天数。
例如：
在此图中，如果我们有3个人可以通过，最小值天数为2。我们将2个人传递到节点2和1个人到节点3。2个人将需要2天才能进入节点3，而1个人将需要1天才能进入Node 3。
我的问题是：如何解决这个问题？是用Max-Flow吗？如果是，如何对问题进行建模，以便可以使用Max-Flow解决问题？
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:
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）