Dijkstra算法的复杂性

Question

Dijkstra算法的复杂性

c++algorithmtime-complexitydijkstrashortest-path

8

我从许多来源读到，如果使用一种朴素的方法来获取最小元素（线性搜索），Dijkstra的最短路径算法也将以O(V^2)的复杂度运行。然而，如果使用优先队列作为数据结构，它可以被优化为O(VLogV)，因为该数据结构将在O(1)时间内返回最小元素，但在删除最小元素后需要花费O(LogV)的时间来恢复堆属性。

我已经在以下代码中实现了Dijkstra算法，用于解决UVA问题，链接如下: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1927:

#include<iostream>
#include<vector>
#include <climits>
#include <cmath>
#include <set>

using namespace std;

#define rep(a,b,c) for(int c=a;c<b;c++)

typedef std::vector<int> VI;
typedef std::vector<VI> VVI;

struct cmp {
    bool operator()(const pair<int,int> &a,const pair<int,int> &b) const {
        return a.second < b.second;
    }
};

void sp(VVI &graph,set<pair<int,int>,cmp> &minv,VI &ans,int S,int T) {
    int e = -1;
    minv.insert(pair<int,int>(S,0));
    rep(0,graph.size() && !minv.empty() && minv.begin()->first != T,s) {
        e = minv.begin()->first;
        minv.erase(minv.begin());
        int nb = 0;
        rep(0,graph[e].size(),d) {
            nb = d;
            if(graph[e][d] != INT_MAX && ans[e] + graph[e][d] < ans[d]) {
                set<pair<int,int>,cmp>::iterator si = minv.find(pair<int,int>(d,ans[d]));
                if(si != minv.end())
                    minv.erase(*si);
                ans[d] = ans[e] + graph[e][d];
                minv.insert(pair<int,int>(d,ans[d]));
            }
        }
    }
}

int main(void) {
    int cc = 0,N = 0,M = 0,S = -1,T = -1,A=-1,B=-1,W=-1;
    VVI graph;
    VI ans;
    set<pair<int,int>,cmp> minv;
    cin >> cc;

    rep(0,cc,i) {
        cin >> N >> M >> S >> T;
        graph.clear();
        ans.clear();
        graph.assign(N,VI());
        ans.assign(graph.size(),INT_MAX);
        minv.clear();
        rep(0,N,j) {
            graph[j].assign(N,INT_MAX);
        }
        ans[S] = 0;
        graph[S][S] = 0;
        rep(0,M,j) {
            cin >> A >> B >> W;
            graph[A][B] = min(W,graph[A][B]);
            graph[B][A] = min(W,graph[B][A]);
        }
        sp(graph,minv,ans,S,T);
        cout << "Case #" << i + 1 << ": ";
        if(ans[T] != INT_MAX)
            cout << ans[T] << endl;
        else
            cout << "unreachable" << endl;
    }
}

根据我的分析，我的算法复杂度为O(VLogV)。STL std::set是作为二叉搜索树实现的。此外，该集合也已排序。因此从中获取最小元素的复杂度为O(1)，插入和删除的复杂度各为O(LogV)。然而，我仍然从这个问题中得到了TLE，而这个问题应该可以在给定的时间限制内以O(VLogV)解决。

这让我深入思考。如果所有节点都相互连接，每个顶点V都有V-1个邻居，那么Dijkstra算法是否会以O(V^2)运行，因为每个顶点必须查看每轮的V-1、V-2、V-3...个节点？

再次思考后，我可能误解了最坏情况下的复杂度。请问有人能就以下问题给予建议吗：

1. Dijkstra算法如何达到O(VLogV)，特别是考虑到上述反例？ 2. 我如何优化我的代码，使其能够达到O(VLogV)的复杂度（或更好）？

编辑：

我意识到我的程序实际上并没有以O(ElogV)运行。瓶颈是由于我的输入处理以O(V^2)运行。Dijkstra部分确实以(ElogV)运行。

- Donald

2个回答

2

通过使用二叉搜索树或堆来改进Dijkstra算法，将导致时间复杂度为O(|E|log|V|) 或 O(|E|+|V|log|V|)，详见Dijkstra运行时间。每条边都必须在某个时刻进行检查。

- Daniel Rodriguez

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wookie919 · Accepted Answer

为了理解Dijkstra算法的时间复杂度，我们需要研究在实现前沿集（即你算法中用于minv的数据结构）时执行的操作：

- 插入（Insert） - 更新（Update） - 查找/删除最小值（Find/Delete minimum）

整个算法执行期间，在数据结构上总共有O(|V|)个插入操作、O(|E|)个更新操作和O(|V|)个查找/删除最小值操作。

最初Dijkstra使用未排序数组实现前沿集。因此，插入和更新操作的时间复杂度都是O(1)，但查找/删除最小值的时间复杂度为O(|V|)，导致整个算法的时间复杂度为O(|E| + |V|^2)。但由于|E| < |V|^2，所以时间复杂度为O(|V|^2)。

如果使用二叉堆来实现前沿集，所有操作的时间复杂度都为log(|v|)，结果为O(|E|log|V| + |V|log|V|)，但由于可以合理假设|E| > |V|，所以时间复杂度为O(|E|log|V|)。

接下来是斐波那契堆，它对于插入、更新和查找最小值操作的摊销时间复杂度都为O(1)，但删除最小值的摊销时间复杂度为O(log|V|)，这样就得到了Dijkstra算法当前已知的最佳时间界限O(|E| + |V|log|V|)。

如果(|V|log|V| < |E|)，则无法在O(|V|log|V|)最坏情况下解决单源最短路径问题，因为该问题具有简单的下限时间复杂度O(|E| + |V|)，即至少需要检查每个顶点和边才能解决问题。