c++ - 多条路径的最短和

Question

设 (x,p1,p2,...pn) 表示有一条从 x 到 p1 的有向边(但不是从 p1 到 x)，一条从 x 到 p2 的有向边等...以及从 x 到 pn 的有向边。假设我们有:

(a,b,c)
(b,d,c)
(c,d,e)
(f,e,h)
(g,f,h,i)
(i,j)

为简单起见，我们假设所有连接节点之间的距离为 1。现在没有从 a 到 g 的连接，反之亦然，但我们可以有两个人们分别从a和g出发，在一个共同点相遇。我们想要找到在一个节点处相交的两条路径的最短总和，使得一条路径从 a 开始，而另一条路径从 g 开始。这个有向图的简单绘图将揭示答案是这两条路径:

a->c->e
g->f->e

总距离为 4。如何编写接受有向图(如上所示)和两个节点(例如 a 和 g 的算法case) 并输出这个答案，我想它的形式可能是 std::make_pair({a,c,e}, {g,f,e})?我试图调整 Dijkstra 的算法来这样做，但没有成功。我欢迎所有想法。

编辑:以上是实际问题的简化版本。这是真正的问题，我不愿意描述它，因为示例图太难阅读了。所以我将在没有示例图的情况下对其进行描述。

在与上图类似但更大的有向图中选择了两个点 A 和 B。从一个点到另一个点没有连接，也没有从 A 和 B 可以到达的公共(public)点。然而，我们确实知道存在点(没有给出多少)N1，N2，... Nk，这样就有一个公共(public)点可以从 A 和 N1 到达，一个公共(public)点可以从 N1 和 N2 到达，.. ., 以及从 Nk 和 B 都可达的公共(public)点。我们想要找到这 k+1 条路径，使得这些路径的总和最小。这才是真正的问题。

Answer 1

您没有正确调整 Dijkstra。而且您不必在每种情况下都为每个节点 x 找到 dist(a,x) 和 dist(g,x)。

在 Dijkstra 的算法中，每个节点都被视为“已访问”或“未访问”，并且搜索一直进行到目的地被“访问”(或无法进一步搜索)。

在变体中，每个节点都是未访问的、A 访问过的、B 访问过的或两者都访问过的。当一个节点变为 Visited-By-Both 时，到它的路径的总和就是搜索的限制；代码将跟踪已找到的最小总和，并在仍在探索的最短路径比该总和长时终止搜索。

我相信这个搜索在最坏的情况下是 O(V logV)。

编辑:“真正的”问题。

我们有 A 和 B，我们正在寻找最小化的 {N}, {x}

(|A, x₁| + |N₁, x₁|) + (|N₁, x₂| + |N₂, x₂|) + (|N₂, x ₃| + |N₃, x₃|)+ ... + (|N_k, x _k| + |N_k, B|)

其中 |x,y| 是从 x 到 y 的最短路径的长度。

现在考虑一个新图，通过向 G 添加反向边来制作:对于 G 中的每条边 x->y，我们添加 y->x(具有相同的权重，但为了我们的目的所有权重都是 1)但是我们不要添加通向 A 的后向边。然后我们从 B 中删除前向边。现在在这个新图上找到从 A 到 B 的最短路径。

此路径从 A 的前向边开始，以到 B 的后向边结束，并且是最短的此类路径。沿着路径，必须有路径在前向边进入并沿着后向边离开的节点；我们标记这些 x_i。并且同样地，必须存在路径从后向边缘进入并且沿着前向边缘离开的节点；我们标记这些 N_i。 (必须至少有一个 N，因为 x₁ 不可能是 x_k，因为我们假设不存在从 A 和 B 都可向前到达的点。)

如果我们将路径分成全前向和全后向路段，我们得到

A-->x₁, x₁<--N₁, N₁-->x₂, x₂<--N₂, N₂-->x₃ , ..., x_k<--N_k, N_k-->B

这条路径的长度是

|A,x₁| + |N₁, x₁| + |N₁,x₂| + |N₂,x₂| + |N₂,x₃| + ... + |N_k,x_k| + |N_k,B|，对于 A、B 的选择是最小的。

因此这些是我们正在寻找的路径(它们可以通过简单的图形 O(V) 转换和 Dijkstra 搜索 (O(VlogV)) 找到)。