如何使用 Dijkstra 算法寻找具有顶点约束的最短路径
How to use Dijkstra's Algorithm for finding shortest path with vertex constraint
我在这个问题上卡了两天了，还是没有任何进展。基本上问题如下：
给定一个无向简单加权连通图，我们必须找到从给定源到给定目的地的最短步行，同时访问给定集合 A 中的至少一个顶点和集合 B 中的至少一个顶点，并添加约束集合 B 中的顶点应该总是在访问集合 A 中的顶点之后出现。
集合 A 和 B 是不相交的，图中可以有既不属于 A 也不属于 B 的顶点。只有一个源和目标顶点。
我尝试将最短路径分解为访问顶点的最短路径，从源 A 中的 v，然后从 v 到 B 中的另一个 w，然后从 w 到目的地。这可以使用分别具有不同起始顶点的 3 遍 Dijkstra 来完成。但是，我必须选择导致 O(VElog(V)) 复杂度的最小 v，其中 V = 顶点数，E = 边数。
我非常困惑如何在 O(E*log(V)) 中执行此操作，因为问题是这样问的，即仅使用 O(1) Dijkstra 运行。有人可以帮我吗？
编辑：我们无法构建新图或修改它，因为有些人建议构建水平图。
我必须以某种方式修改 Dijkstra 例程来解决这个问题。
Graph. Blue vertices are the set A, purple ones set B. Home is 0 and Destination is 8
例如，在此图中（参见 link），最短步行应为：0 -> 1 -> 0 -> 3 -> 6 -> 7 -> 8，总成本 = 6
解决此类问题的最简单（对我而言）方法是将图顶点分成 "levels"（就像建筑物中的故事），并可能在多个级别之间复制一些顶点。
在你的例子中，将有 5 个级别，第 1、3 和 5 级包含所有顶点，而第 2 级只有 A 顶点，第 4 级只有 B。起始顶点在第 1 级，结束在级别 5. 原始边缘在每个级别内和相邻级别之间被复制。
修改图中的任何路径都经过一个A顶点，然后再经过一个B顶点，因为任何路径都必须按顺序通过所有5个级别。
这种安排不关心除了所需顺序中的强制对之外是否还有任何顺序的附加 A 和 B 顶点（因此允许 x-x-x-A-B-A-B-x-x-x）。如果您需要排除这些，请从第 1 层和第 3 层中删除所有 B 顶点，并从第 3 层和第 5 层中删除所有 A 顶点。
作为@n.'pronouns'米。指出，我们可以通过图形分层来解决这个问题。
特别针对我的情况，只需添加一个新的源顶点并将该源顶点的边添加到属于原始图 A 的所有顶点的边。这些边的权重将与原始图中从原始源到该顶点的最短路径相同。
类似地，您添加一个新的目标顶点并将所有 B 顶点的边添加到这个新顶点，并且边的权重再次是原始图中从 B 顶点到原始目标顶点的最短路径。
现在，如果您 运行 Dijkstra 从新源到新目的地，您会看到在 B 顶点最终到达新目的地之前至少会访问一个 A 顶点。这条路径确实是最短路径。
我在这个问题上卡了两天了，还是没有任何进展。基本上问题如下： 给定一个无向简单加权连通图，我们必须找到从给定源到给定目的地的最短步行，同时访问给定集合 A 中的至少一个顶点和集合 B 中的至少一个顶点，并添加约束集合 B 中的顶点应该总是在访问集合 A 中的顶点之后出现。 集合 A 和 B 是不相交的，图中可以有既不属于 A 也不属于 B 的顶点。只有一个源和目标顶点。
我尝试将最短路径分解为访问顶点的最短路径，从源 A 中的 v，然后从 v 到 B 中的另一个 w，然后从 w 到目的地。这可以使用分别具有不同起始顶点的 3 遍 Dijkstra 来完成。但是，我必须选择导致 O(VElog(V)) 复杂度的最小 v，其中 V = 顶点数，E = 边数。 我非常困惑如何在 O(E*log(V)) 中执行此操作，因为问题是这样问的，即仅使用 O(1) Dijkstra 运行。有人可以帮我吗？
编辑：我们无法构建新图或修改它，因为有些人建议构建水平图。 我必须以某种方式修改 Dijkstra 例程来解决这个问题。 Graph. Blue vertices are the set A, purple ones set B. Home is 0 and Destination is 8 例如，在此图中（参见 link），最短步行应为：0 -> 1 -> 0 -> 3 -> 6 -> 7 -> 8，总成本 = 6
解决此类问题的最简单（对我而言）方法是将图顶点分成 "levels"（就像建筑物中的故事），并可能在多个级别之间复制一些顶点。
在你的例子中，将有 5 个级别，第 1、3 和 5 级包含所有顶点，而第 2 级只有 A 顶点，第 4 级只有 B。起始顶点在第 1 级，结束在级别 5. 原始边缘在每个级别内和相邻级别之间被复制。
修改图中的任何路径都经过一个A顶点，然后再经过一个B顶点，因为任何路径都必须按顺序通过所有5个级别。
这种安排不关心除了所需顺序中的强制对之外是否还有任何顺序的附加 A 和 B 顶点（因此允许 x-x-x-A-B-A-B-x-x-x）。如果您需要排除这些，请从第 1 层和第 3 层中删除所有 B 顶点，并从第 3 层和第 5 层中删除所有 A 顶点。
作为@n.'pronouns'米。指出，我们可以通过图形分层来解决这个问题。 特别针对我的情况，只需添加一个新的源顶点并将该源顶点的边添加到属于原始图 A 的所有顶点的边。这些边的权重将与原始图中从原始源到该顶点的最短路径相同。 类似地，您添加一个新的目标顶点并将所有 B 顶点的边添加到这个新顶点，并且边的权重再次是原始图中从 B 顶点到原始目标顶点的最短路径。 现在，如果您 运行 Dijkstra 从新源到新目的地，您会看到在 B 顶点最终到达新目的地之前至少会访问一个 A 顶点。这条路径确实是最短路径。