如果权重为负，只要不存在循环，可以使用 Dijkstra 算法吗？

Question

更新：我真的搞砸了原来的问题。我原来的标题是“为什么我们首先对非循环加权有向图最短路径问题进行拓扑排序？”但我的问题内容是关于Dijkstra算法的。希望自从我更改了标题后，问题就以对其他人有用的方式进行了更新。更新后的问题标题的答案是“是”。

原问题：

为什么我需要先进行拓扑排序？ （请参阅此处的代码） 我不能只使用如下所示的 Dijkstra 算法吗并完全避免拓扑排序（语法有点混乱，但你明白了）

MinIndexedPriorityQueue waitingEdges = new MinIndexedPriorityQueue
Graph g //some weighted directed graph
double[] distTo = new double[g.vertexCount]
Edge[] edgeTo = new Edge[g.vertexCount]
int source = //init to some value

void minPathInit()
    init distTo to double.MAX_VALUE
    //init first node
    distTo [source] = 0
    visit(source)
    while waitingEdges.count>0
        int vertex = waitingEdges.dequeue()
        relax(vertex )

void relax(v) //note that visit has been renamed to relax
    for each edge in graph.getEdgesFrom(v)
        int to= edge.to
        if edge.weight + distTo [edge.from]<  distTo [to]
            distTo[to] = edge.weight + distTo [edge.from]
            edgeTo[to] = edge
            if waitingEdges.contains(to)
                waitingEdges.change(to,  distTo[to] )
            else
                waitingEdges.enqueue(to,  distTo[to] )


//after everything is initialized
getPathTo(v)
    if not hasBeenVisited[v]
        return null
    Stack path = new Stack
    while edgeTo[v] != source
        path.push(edgeTo[v])
        v = edgeTo[v].from
    return path

我可以理解为什么 Dijkstra 算法无法处理负循环（因为它会陷入无限循环），但如果没有负循环周期，为什么它会如图所示失败（并且首先需要拓扑排序）

更新：好的，我可以看到我已经搞砸了这个问题，所以我会尝试用一个修复它更新。感谢您花时间为我指出漏洞。我错误地认为 AcycloSP 在删除拓扑排序时成为 Dijkstra 算法，但事实并非如此案件。

然而，我关于 Dijkstra 算法（使用上面显示的版本）的问题仍然存在。为什么只要没有循环，即使有负权重也不能使用？这里有 Dijkstra 算法的 java 版本。我的例子与此非常相似（因为我是在这本书中了解到它的），但他的例子对于你们中的一些人来说可能更容易阅读。

Answer 1

您没有在原始算法中进行任何拓扑排序。但在非循环图的情况下，您可以将运行时间减少到 O(V) （而原始运行时间为 O(|V|*log(|V|)）。
原因是您在 O(|V|) 时间内排序，然后您可以使用该顺序，并且不需要任何堆（或优先级队列）。因此总时间减少到 O(|V|)。

Answer 2

Dijkstra 算法似乎不需要拓扑排序。也许这样做可以避免您在实现中遇到的错误。

Dijkstra 算法不支持负路径成本，但确实处理循环。当它发现有一条更短的路径到达节点时，它会停止。循环路径不会更短并在那里停止（前提是成本非负）

Answer 3

无法将 Dijkstra 算法与负权重一起使用。
数百人尝试过，但没有人成功。

如果您有否定，请使用贝尔曼-福特算法。重量