在带负权重的加权DAG中寻找两个节点之间的最短路径

Question

我有一个有向无环图（DAG），里面的边有权重，这些权重可以是正数也可以是负数。我有一个起始节点叫做根节点（root），还有一个目标节点叫做目标节点（goal）。我需要找到一条从根节点到目标节点的路径，这条路径的总权重要尽可能小（如果总权重是负数，那就更好了），而且这个过程要在 O(V + E) 的时间内完成。

我想出了以下的伪代码，这个代码几乎和 Dijkstra 算法一样，只不过它只关注目标节点，而不是所有节点。

Q = PriorityQueue()
Q.insert(root, 0)
while (Q is not empty) {
    node = Q.extractMin()
    if (node == goal) {
        return path from node to goal
    }
    else {
        for (x in adjacent[node]) {
            Q.insert(x, weight[x])
    }
}

这个算法有效吗？另外，我不太确定它是否真的能在 O(V + E) 的时间内完成。

附加问题：如果在我遍历图的过程中，当前节点的权重总和必须始终小于等于 k，那我该如何找到一条路径，使得这条路径的权重在整个过程中始终小于等于 k，并且在图中存在的情况下，仍然能在 O(V + E) 的时间内完成？

Answer 1

这里的关键是无环有向图。简单来说，如果你按照一种叫做拓扑排序的顺序来放松（也就是更新）图中的边，比如说把d(w)设置为d(w)和(d(v) + length(v->w))中的较小值，那么每条边一旦被放松，就会一直保持放松的状态。根据贝尔曼-福特算法的正确性证明，这意味着距离标签d是正确的。

Answer 2

有一个非常简单的方法可以解决大卫提到的递归问题：我们可以使用深度优先搜索（DFS）加上记忆化技术，这样在每次处理当前节点时，所有需要解决的子问题的结果都已经知道了。这种方法自然就形成了我们需要的拓扑顺序：

for all nodes x: 
    dis[x] = UNKNOWN
def dfs(x):
    if x == goal: return 0
    if dis[x] != UNKNOWN: return x
    dis[x] = infinity
    for all edges (x,y) with weight w:
        dis[x] = min(dis[x], w + dfs(y))
    return dis[x]

最终的结果就是 dfs(root)

如果你想找到一条最短路径，并且这条路径的权重从来不超过 k，你可以从目标点反向进行深度优先搜索：

for all nodes x: 
    dis[x] = UNKNOWN
def rdfs(x):
    if x == root: return 0
    if dis[x] != UNKNOWN: return x
    dis[x] = infinity
    for all edges (y,x) with weight w:
        dis[x] = min(dis[x], w + rdfs(y))
    if dis[x] > k:
        dis[x] = infinity
    return dis[x]

解决方案是 rdfs(goal)。