修改的最短路径算法(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的另一个节点。

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