关于带负权值的单源最短路径算法

Question

老师，你好。我有个疑问，带负权值的单源最短路径算法，用深度优先算法来实现，是否复杂度会比Bellman-Ford算法更加小呢？

深度遍历部分伪代码如下：

void DFT(int node)
{
    //visited为bool数组，标记该节点是否已遍历过，若是，则有负权环
    if(visited[node] || hasNegativeCircle) 
    {
        hasNegativeCircle = true;
        return;
    }
    else visited[node] = true;

    Graph::Iterator iter(graph, node);
    //遍历该节点所有边
    for(auto e = iter.begin(); !iter.end(); e = iter.next())
    {
        int other = e->other(node);
        //这里的from是int数组，标识该节点的前一个节点，-1为初始值
        //若满足松弛条件，则往下搜索该节点
        if(-1 == from[other] || distTo[other] > distTo[node] + e->wt())
        {
            from[other] = node;
            distTo[other] = distTo[node] + e->wt();
            DFT(other);
        }
    }
    //递归返回时，应将该节点标记为未访问
    visited[node] = false;
}

根据邻接表图的遍历，复杂度应该是O(V + E)，比O(VE)小。用教程上的测试用例也能跑过。只是不知道是否有其他的缺陷存在，能否请老师帮忙分析一下呢？谢谢！

Answer 1

liuyubobobo 2018-12-16 15:02:06

这可不是一个O(V+E)的算法。这是一个回溯算法。因为最后visited[node]置回了false，所以，不能保证每个节点都只访问一次！事实上，一个节点在多少条路径上出现过，就会被访问多少次。这是一个指数级别的算法：）

可以尝试在一个更大的图上跑一下，比如含有1000个节点的图，应该和BellmanFord算法在实践效率上有明显的差异：）

大赞实验精神和独立思考！继续加油！：）

• 提问者 从零开始的工程师 #1

  原来如此！测试了下，节点比较多的情况下，BellmanFord效率明显比回溯法高很多。多谢老师指点！