algorithm - 图中受约束的最短距离

Question

我在编码站点遇到了这个问题，但我不知道如何解决它。该社论不可用，我也无法在网上找到任何相关文章。所以我在这里问这个问题。

问题:

You have a graph G that contains N vertices and M edges. The vertices are numbered from 1 through N. Also each node is colored either Black or White. You want to calculate the shortest path from 1 to N such that the difference of black and white nodes is at most 1.

很明显，直接应用 Dijkstra 算法是行不通的。任何帮助表示赞赏。谢谢!

Answer 1

我们可以考虑一个修改过的图并在这个图上运行 Dijkstra:

对于原始图中的每个节点，修改后的图会有多个元顶点(理论上是无限多)，每个元顶点对应不同的黑白差异。您只需在使用 Dijkstra 浏览图形时创建节点。因此，您不需要无限多的节点。

然后边缘就非常简单了(您也可以在探索时创建它们)。如果您当前处于黑白差异为 d 的节点，并且原始图形具有到白色节点的边，则您创建到相应节点的边，黑白差异为 d -1。如果原始图有一条到黑色节点的边，您可以在修改后的图中创建一条到相应节点的边，黑白差异为 d+1。您不一定需要将它们视为不同的节点。您也可以将 Dijkstra 变量存储在按黑白差异分组的节点中。

以这种方式运行 Dijkstra 将为您提供到具有任何黑白差异的任何节点的最短路径。一旦您到达具有可接受的黑白差异的目标节点，您就完成了。