图上用权重变化的最短路径

Question

我试图解决当地的编程竞赛问题。问题基本上是在加权图中找到最短路径。我对这些类型的问题很陌生，我想我可以使用Dijkstra的算法。但是，有一个小的复杂性 - 某些值是不同的，这取决于当前路径的情况。

问题

有两种类型的权重：正常体重和权重与条件（我们姑且称之为K）。条件是这样的：一旦你移动通过边的权重为K，所有类型K的所有其他权重的值都为0.这带来了一些问题，因为表观最短路径可以通过带有类型K的权重的边的组合。

例

下面是这种类型的问题。如果没有权重会改变它们的价值，我们可以很容易地找到与Dijkstra最短的路径。然而，当权重K改变它们的值时，我们可以找到更短的路径，因为在移动通过边缘A-C之后边缘C-D的权重为0。

问题

我怎样才能找到最短路径？

我可以在这里使用Dijkstra算法还是使用A *或BFS等其他算法更好？

Answer 1

有多少K？

我只有一个，Dijkstra很好。 我会补充说，BFS不能很好地处理重量。

提醒：Dijkstra找到从顶点到所有顶点的最短路径。

运行Dijkstra两次并为每次运行定义一个不同的wight函数。首先，K值的wight函数是无限的。对于K值的第二个wight函数为0.

比较run1到run2 + K的结果。

这是真实的，因为如果最短路径没有K首先运行会找到它。否则是K，第二次运行会找到它。无论哪种方式，算法会找到它。