修改后的最短路径算法（Dijkstra算法）

Question

修改后的最短路径算法（Dijkstra算法）

7

我的问题是，我有一个具有非负边长的有向图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）时都会更新此值）。但是，由于算法没有跟踪我们看到的所有可能的具有一个或更少节点的路径，而只是最短距离路径，因此这似乎并不起作用。

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

此外，这是一个家庭作业问题，因此请勿发布整个解决方案，我只是在寻求指导。

- Niehra

很棒的问题！你对复杂度有任何限制吗？ - Andrew Walker

它应该具有与 Dijkstra 算法相同的时间复杂度。 - Niehra

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AlexAlvarez · Accepted Answer

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

首先，我认为您目前的想法无法解决这个问题。因此，我将尝试引导您采用不同的方法。考虑Dijkstra是一个好主意，但是不要修改Dijkstra，而是考虑转换图形，以便在新图中运行Dijkstra可以解决原始问题。

如何消除集合P的原始限制？嗯，重要的是图是有向的（或者至少对于我的想法是这样）。考虑一种方法来转换图形，使得如果您进入P的一个节点，则不能再进入另一个P节点。

最后一个想法，但仍未提供解决方案。考虑复制图形，也许删除一些边缘并以某种方式连接两个副本的节点。