修改后的最短路径算法，禁止路径

Question

我们得到了一个图 G = (V, E)，其中每条边都与一些正权重 (W[i] > 0) 相关联。我们被要求找到从 A 到 B 的最短路径，前提是我们遵循以下条件：

我们也给出了一些禁止路径，比如 x。目标是最短路径不应包含任何禁止路径作为其子路径。

例如：考虑具有 4 个顶点和 5 个边的图 G (1, 2, 1), (2, 1, 1), (1, 4, 5), (1, 3, 1.5), (3, 4, 1)。这里，括号中的第 3 个实体表示 'u' 和 'v' 之间的边的权重。我们要求找到1和4之间的最短路径，禁止路径列表只包含路径1->3->4。

从1到4的路径是1 -> 4, 1 -> 2 -> 3 -> 4, 1 -> 3 -> 4.

其中，只有1st 2是有效路径，其中最短路径为1 -> 2 -> 3 -> 4，总权重为3.0。

上面的任务有高效的算法吗？请用复杂性分析描述算法。如果您也能提供一个代码，我将不胜感激。

Answer 1

您可以对图表进行预处理，将禁止路径嵌入其中。对于每条禁止路径，您复制属于它的顶点，然后删除一些边。重复将具有特殊含义：沿着重复边行走意味着您已经沿着禁止路径到达顶点并且您不能沿着它的最后一条边行走。如果你沿着原来的边缘行走，那么你已经来到了禁止路径中间的某个地方，所以它不会影响你。为实现这一点，您将所有传入边放到重复路径中，除了从它的第一个顶点到它的第二个顶点的边。但是您从原始路径中删除了该边缘。

a forYou 将禁止路径的顶点拆分为几个虚拟顶点并删除一些边。假设在以下图形路径 ABC 中被禁止：

A-->B-->C
D->/

然后你将 B 拆分为 BA 和 BD（取决于你从哪个顶点来到 B）并删除 BA->C 边。

A->BA  /->C
D->BD-/

现在您可以在该预处理图上使用经典的 dijkstra。

更复杂的例子，假设 ABCF 被禁止：

    G->\
A-->B-->C-->F
D->/ \->E

所以我们将B和C复制为禁止路由的内部顶点，我们删除A->B边，只留下A->B'。我们还将所有其他传入边丢弃到 B' 和 C'，但我们保留 B'->E 边，因为它远离禁止路线。我们还删除了 C'->F 边。

 /->B'-->C'
|    \------->\
|              \
|   G->\        \
A   B-->C---->F  \
D->/ \----------->E

修改后的最短路径算法，禁止路径

Modified Shortest path algorithm, forbidden paths

graph

dijkstra

shortest-path