双目标最短路径问题的类型判定及NP-hard属性咨询

嘿，咱们来一步步拆解你的问题：

首先，从你给出的总代价公式来看，你已经把双目标（时间+事故概率）转化成了一个单目标的加权最短路径问题——虽然原始问题有两个维度，但你通过Total cost = time + (路径事故概率)*(事故时间成本)这个公式，把两个指标合并成了单一的“总代价”权重，所以本质上这就是个标准的带权最短路径问题，每条边的权重可以预先用这个公式计算出来。

不过如果咱们聊原始的未合并版本（同时追求时间最短、事故概率最低，找帕累托最优路径），那属于多目标最短路径问题，但你的场景已经做了单目标转化，核心还是前者。

接下来聊你关心的NP-hard问题：

• 只要你的图里没有负权边，这个问题完全可以用Dijkstra算法在多项式时间内解决（优化后的时间复杂度是O(M + N log N)，N是节点数，M是边数），绝对不属于NP-hard问题。
• 那什么时候会涉及NP-hard？只有当你的路径事故概率是联合概率计算（比如各边概率乘积）且没有转化为线性代价项，或者图中存在负权环的时候，才会出现复杂情况，但你的公式已经把概率项转化成了线性加法项，只要计算后的边总代价没有负环，用常规最短路径算法就能搞定。

举个实际操作的例子：针对你给出的图（黑色为旅行时间，红色为事故概率），你可以先给每条边计算单一代价：边总代价 = 黑色时间值 + (红色概率值) * 事故时间成本，然后整个问题就变成了找从起点到终点的最小总代价路径，直接用Dijkstra（无负权）或者Bellman-Ford（有负权但无负环）就能解决，完全是多项式时间可解的。

补充一句：如果是未合并的多目标版本（找帕累托最优路径集合，没有绝对最优解），算法复杂度会高一点，但也不属于NP-hard，只是需要用标签设置这类算法来枚举所有帕累托路径。但你的场景已经转化为单目标，所以不用考虑这个~

内容的提问来源于stack exchange，提问作者CSDUG