我们有一个有向加权图，其中两个节点之间的边可以具有多个可能的成本值(更准确地说，最多 2 个成本)。我需要使用 Dijkstra 算法的时间相关变体，它可以处理从一个节点到另一个节点的两种可能方式，节点之间的成本(边成本)取决于我们到达源节点的时间和我们将要使用的边缘类型。当从一个节点遍历到另一个节点时，只会选择这些边中的一条，并将其成本添加到相同的总成本中。
我目前将一条边的两种可能成本建模为相同节点之间的两条单独的边。
我发现了一个类似的问题here并建议通过复制节点来扩充图形。然而，这不允许返回到原始图，并且意味着复制所有节点以及它们与原始节点之间可能存在的边的开销。
对于如何以尽可能少的开销解决这个问题，您有什么建议吗？ (原图估计很大)
谢谢
编辑: 我在第一段中提供了有关该问题的更多详细信息
最佳答案
出于算法目的，您可以安全地忽略两个成本中最大的一个。
假设在两个顶点之间存在一条使用最大成本的最短路径，您可以将其更改为使用最小成本并且路径将花费更少，这与假设相矛盾。
关于algorithm - 修改 Dijkstra 算法以处理具有不止一种可能成本的边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23376897/