graph - 修改的最短路径算法(Dijkstra's)

Question

所以我的问题是我有一个带有 的有向图 G非负 边长度，我希望找到两个节点 u 和 v 之间的最短路径，以便它们只通过图中的一个标记节点。

如果我们没有涉及标记节点的条件，这个问题可以使用 Dijkstra 算法轻松解决。

procedure dijkstra(G, l, s)
Input: Graph G = (V, E), directed or undirected;
positive edge lengths {le : e ∈ E}; vertex s ∈ V
Output: For all vertices u reachable from s, dist(u) is set to the distance from s to u.

for all u ∈ V :
    dist(u) = ∞
    prev(u) = nil
dist(s) = 0
H = makequeue(V ) (using dist-values as keys)
while H is not empty:
    u = deletemin(H)
    for all edges (u, v) ∈ E:
        if dist(v) > dist(u) + l(u, v):
            dist(v) = dist(u) + l(u, v)
            prev(v) = u
            decreasekey(H, v)

此外，为了处理这种情况，我正在考虑添加一个值，该值给出从 s 到 u 的当前最佳路径中的当前节点数(每当 dist(u) 更新时都会更新)。但这似乎不起作用，因为该算法没有跟踪我们在一个或更少节点上看到的所有可能路径，而只是跟踪距离最短的路径。

我的问题是我是否在正确的轨道上，只需要额外修改算法？或者是否有另一种算法可以更轻松地实现这一目标？

另外，这是一个家庭作业问题，所以请不要发布完整的解决方案，我只是在寻找指导。

Answer 1

由于您不想要整个解决方案，我会给您一些提示。停止阅读每个段落，然后尝试解决问题，我将尝试从更一般的提示转向更具体的提示。

首先，我认为您目前的想法不能解决问题。因此，我将尝试引导您采用不同的方法。考虑 Dijkstra 是个好主意，但与其修改 Dijkstra，不如考虑 变换图形 所以要实现在新图中运行 Dijkstra 可以解决原始问题。

如何去除集合P的原始限制？好吧，重要的是图形是有向的(或者至少对于我的想法)。想一种变换图形的方法，强制进入P的一个节点，就不能再进入P的另一个节点。

最后一个想法，仍然没有给出解决方案。考虑复制图，也许删除一些边并以某种方式连接两个副本中的节点。