根据路径长度增加额外成本

Question

我有一个图/网络，它显然由一些节点和一些边组成。每条边都有一个权重，或者在本例中是一个成本。每条边也有一个附加到它的距离和一个类型。因此，基本上，重量/成本是根据边缘的距离以及两种类型边缘的一些其他度量预先计算的。

然而，在我的情况下，我希望增加一些额外的成本，比如说每100米左右，但只适用于一种边缘。但是我甚至不确定是否有可能根据Dijkstra等算法中路径中先前步骤的总和添加额外的成本/距离？

我知道我可以把成本分成每一个distance unit，从而得到一个大致的估计。存在的问题是边缘情况，在距离199处的成本几乎是在每100个距离处增加成本的两倍，即在100和200处增加成本。

但是也许有其他方法可以解决这个问题？

Answer 1

我认为您不能使用Dijkstra实现这一点，因为您需要验证不变量，这是正确性所必需的（参见例如wikipedia）。在每一步中，Dijkstra都建立在这个不变量的基础上，这个不变量或多或少地表示，所有“已经找到的路径”都是最优的，即最短的。但是，为了证明它在“按边缘类型和覆盖距离计算的额外成本”的情况下不成立，让我们看一个反例：

假设我们有两种边，第一种(-

start -1-> u_1 
start -1-> u_2 
start -1-> u_3 
... 
start -1-> u_7 
u_7 -1-> v 
start =7=> v 
v =4=> end

当我们使用Dijkstra（我跳过所有中间步骤）将start作为开始节点，将end作为目标，我们将首先检索路径start=7=

简言之，Dijkstra是不适用的——即使您修改了算法，将“已找到的路径”考虑在内，以便检索下一条边的成本。

也许您可以围绕Dijkstra的一个变体构建您的算法，它通常检索多个（次优）解决方案。首先，您需要扩展Dijkstra，以便它考虑已经找到的路径。（在此函数中，将cost=weight（v，u，e）替换为cost=weight（v，u，e，paths[v]），并编写一个合适的函数，根据前面的路径和考虑的边计算惩罚）。然后，从原始最优解中删除边，并迭代该过程以找到新的备选最短路径。但是，除了惩罚类型中的边之外，我看不到从图中选择要删除的边的简单方法，而且运行时的复杂性可能非常糟糕。