java - 在具有负权重的加权 DAG 中查找两个节点之间的最短路径

Question

我有一个带加权边的连接 DAG。权重可以是正数或负数。我有一个名为 root 的起始节点和一个名为 goal 的目标节点。我需要找到一条从根到目标的路径，使净重在 O(V + E) 时间内尽可能小(如果净重为 -ve 则更好)。

我想出了以下伪代码，它几乎与 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)。

P.S.:如果我遍历图形时到当前节点的权重应该始终 <= k 怎么办？我怎样才能找到最短路径，使得该路径在整个路径中的权重在 O(V + E) 时间内始终 <= k，前提是它存在于图中？

Answer 1

有一个非常简单的算法可以解决 David 的回答中描述的递归问题:我们可以使用带有内存的深度优先搜索来确保每次我们需要解决当前节点结果所需的所有子问题都是已知的。这隐含地导致了我们需要的拓扑顺序:

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的最短路径，您可以使用来自目标的反向 DFS:

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)。