如何求解多起点多终点路径不交叉的最短路径总长度最优问题

你所描述的属于带冲突约束的多组源汇对最短路径统筹问题，以下是几类成熟的适用算法：

• 整数多商品流算法（Integer Multi-Commodity Flow, IMCF）
  是这类问题的标准精确求解方案：你可以把每个起点对应的所有起终点对定义为一类「商品」，建模时目标函数设置为所有路径的总长度最小，约束条件包含：流守恒约束（每个终点的流入量等于1，对应唯一路径到达）、所属起点约束（每个终点的路径只能从其对应的唯一起点出发）、交叉约束（根据你的「不可交叉」定义，若为几何交叉则将交叉边对设置为互斥占用约束，若为拓扑上不可共享节点/边则设置对应容量为1，允许重叠即允许边容量≥2）。规模较小的图可以直接用Gurobi、Cplex等求解器得到全局最优解。
• 协同A算法（Cooperative A*, CA*）*
  适合大规模图、对求解速度要求高的场景：和你之前用的逐次A不同，协同A会统一维护所有路径的空间占用状态，在搜索过程中全局检测不同路径的冲突，通过预留空间窗口、调整搜索优先级的方式避免后续路径过度绕路，总长度的优化效果远好于逐次求解的A*，如果是网格图类场景还可以搭配跳跃点搜索（JPS）加速计算。
• 多源路径树联合优化算法
  针对你的「每个终点唯一对应一个起点」的专属特性开发的轻量方案：首先为每个起点独立生成初始最短路径树，再全局检测不同路径树之间的交叉冲突，对存在冲突的路径做局部迭代调整，每次调整选择总长度增量最小的方案，直到所有冲突消除，计算复杂度远低于前两类算法，适合超大规模的路网、管网类场景。
• 启发式智能优化算法
  若你的场景允许近似最优解、约束规则复杂，可以选择遗传算法、蚁群算法等：将所有路径的组合作为种群个体，目标函数设置为总长度最小+冲突惩罚项，迭代进化得到接近最优的解。

如果你定义的「不可交叉」是平面几何层面的线段交叉（而非拓扑层面共享边/节点），需要提前对图做预处理，标记所有存在几何交叉的边对，在上述所有算法的约束中加入边对互斥占用规则即可。

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