只要没有周期，如果权重为负，您可以使用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的算法不能处理负循环(因为它会陷入无限循环)，但如果没有负循环，为什么它会失败(并要求首先进行拓扑排序)

Update: Ok，我可以看到我把这个问题搞砸了，所以我会尝试用更新来修复它。谢谢你花时间给我指出那个洞。当去掉拓扑排序时，我错误地认为AcyclicSP成为Dijkstra的算法，但事实并非如此。

然而，我对Dijkstra算法(使用上面显示的版本)的疑问仍然存在。为什么即使权值是负的，只要没有循环就不能用它呢?这里有一个Dijkstra算法的java版本。我的例子与这个非常相似(因为我是从这个人的书中了解到的)，但他的例子可能对你们中的一些人来说更容易阅读。

Answer 1

在原始算法中不做任何拓扑排序。但在a循环图的情况下，你可以将运行时间定为O(V)(而原始运行时间为O(|V|*log(|V|))。原因是您在O(|V|)时间内排序，然后您可以使用该顺序，并且不需要任何堆(或优先级队列)。所以在整个时间内减小到0 (|V|)

Answer 2

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

Dijkstra的算法不支持负路径代价，但是可以处理循环周期。当它发现到某个节点有一条更短的路径时，它就会停下来。一个循环路径不会更短，并且在那里停止(前提是成本是非负的)

Answer 3

不能使用负权值的Dijkstra算法。数百人尝试过，但没有一个成功。

如果你的值为负，使用Bellman-Ford算法。重量