algorithm - 如果没有循环，如果权重为负，是否可以使用 Dijkstra 算法？

Question

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

原始问题:

为什么要先做拓扑排序？ (see code here)我不能只使用下面显示的 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 的算法不能处理负循环(因为它会陷入无限循环)但是如果没有负循环，为什么它会如图所示失败(并且首先需要拓扑排序)

更新: 好吧，我知道我搞砸了这个问题，所以我会尝试通过更新来修复它。感谢您花时间为我指出漏洞。我误以为AcyclicSP去掉拓扑排序就变成了 Dijkstra 算法，而事实并非如此。

但是，我对 Dijkstra 算法(使用上面显示的版本)的问题仍然存在。为什么即使有负权重只要没有循环也不能用呢？有Dijkstra's algorithm here的Java版本.我的与此非常相似(因为这个人的书是我了解它的地方)但他的示例对于你们中的一些人来说可能更容易阅读。

Answer 1

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