我正在编写一个基于回合的策略游戏，我有一个特殊的单对最短路径问题。我有一个带有非负非零边权重的加权有向图，这里有多个旅行者，即具有不同运动类型的单元作为一个群体一起旅行。图表的每条边对不同的单位都有不同的权重，具体取决于移动类型。
通常人们会使用例如。Dijkstras算法解决最短路径问题。但是由于多个单元作为一个组一起移动并且每个单元的边权重不同，因此最佳路径可能与任何单个单元单独移动的最佳路径不同。从下面可以看出
红色和绿色从 S 移动到 D。单独红色移动的最佳路径是成本为 2 的 SAD，单独绿色移动的最佳路径是成本为 2 的 SCD。然而，在这两种情况下，另一个单位移动成本为 5，因此单位一起移动的最佳路径是 SBD，最大移动成本为 4。
每个单位类型每转不同数量的移动点似乎不是问题，因为边缘权重可以标准化。这可以表述为线性程序并用单纯形算法解决吗？看起来我们会有多个目标函数，我们希望最小化最大值。但是可能有更简单的解决方案吗？