查找总成本最小的不相交图

Question

这是一个

优化/最小流量问题。对于这个有向图，我希望所有顶点只访问一次，但这个图可以存在多个不相交的路径，并且每个路径对其总成本都有限制。此问题的目标是最小化所有不相交路径的总成本。

我

只知道如何找到Dijkstra最短路径，我不确定是否可以应用类似的原理。请帮助我并分享您对此的看法。

非常感谢！

Answer 1

在我看来，您正在描述一个车辆路径问题，其中每条路线都受到车辆容量或最大行驶时间的限制。看看 https://en.wikipedia.org/wiki/Vehicle_routing_problem。