各位大牛，最近做图的最优路径相关，有没有针对多目标约束的相关算法？举个例子，就是交通规划中，时间<1 小时，并且油耗<1 升。找了一圈一般图论中的算的都是最优路径，不太满足需求。有相关的论文也行

[microxiaoxiao]

[enki0423]

网络流？

[microxiaoxiao]

对，现在是单权可以通过一般的图算法狄克斯特拉算法实现，topN 最优也可以利用相关改进算法实现，但是深入研究发现针对多约束的资料比较少，一种可行的思路是直接找到单权的 topN 直接计算剩余约束是否满足，就是想知道是否有比较可靠的理论算法，毕竟工程思路怕不够灵活。

[heart4lor]

感觉有点像网络流，又有点像 dp ；既然提到了 dijkstra ，以 dijkstra 为例，是否可以考虑松弛时直接拓展`if (dist[v] > dist[u] + weight)`中的 dist 和 weight 到多维即可？

[kilasuelika]

图的路径优化可以转化为一个整数规划。
以前用过 google 有个 or-tools ，有现成的路径规划器，里面可以进行约束。

[txx]

最小费用流？

[vance123]

用求解器吧，比算法灵活多了

[guoph]

这个是运筹学（ Operations Research, OR ）的研究问题。可以使用混合整数规划（ Mixed Integer Programming, MIP ）建模，用 MIP 求解器求解。常用的求解器有商业的 Gurobi ，CPLEX ，和开源的 SCIP ，OR-Tools 等。以上求解器的文档或许能够给你提供些有帮助的例子。

[microxiaoxiao]

@heart4lor 这个思路考虑过，但是要定义一个节点新距离不好定义，选最小。

[microxiaoxiao]

@guoph @vance123 @kilasuelika 谢谢，是一些不错的工具集，主要就是想自己实现，黑盒子不好工程化，动态添加，删除节点什么的，可以参考一下。目前先就按 topN 或者深度优先+回溯的思路先选一个满足约束条件的路径也行，不要最优也行，就是感觉有点土办法。