Dijkstra 算法的复杂性

Question

我从许多资料中了解到，如果使用朴素的方式获取最小元素（线性搜索），Dijkstra 的最短路径也将运行复杂度为 O(V^2)。但是，如果使用优先级队列，它可以优化为 O(VLogV)，因为此数据结构将在 O(1) 时间内 return 最小元素，但需要 O(LogV) 时间来恢复堆属性删除最小元素后。

我在下面的代码中针对 UVA 问题实现了 Dijkstra 算法 link：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 个邻居怎么办？它不会在 O(V^2) 中使 Dijkstra 算法运行因为每个顶点都必须查看 V-1、V-2、V-3... 节点每一轮吗？

再想想，我可能误解了最坏情况下的复杂性。有人可以就以下问题给我建议吗：

对于上述反例，Dijkstra 的算法 O(VLogV) 表现如何？
我如何优化我的代码以使其达到 O(VLogV) 复杂度（或更好）？

编辑：

我意识到我的程序毕竟不在 O(ElogV) 中运行。瓶颈是由我的输入处理引起的，O(V^2) 中的运行s。 dijkstra 部分确实运行s in (ElogV).

Answer 1

通过使用 BST 或堆改进 Dijkstra 将导致时间复杂度，如 O(|E|log|V|) 或 O(|E|+|V|log|V|)，请参阅 Dijkstra's running time。必须在某个点检查每条边。

Answer 2

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

插入
更新
Find/Delete 最低

在整个算法持续时间内，数据结构上总共有 O(|V|) 次插入，O(|E|) 次更新，O(|V|) Find/Delete 次最小值。

Dijkstra 最初使用未排序数组实现 Frontier 集。因此插入和更新是 O(1)，但最小 Find/Delete 是 O(|V|)，结果是 O(|E| + |V|^2)，但是由于 |E| < |V|^2，你有 O(|V|^2) .
如果使用二进制最小堆来实现 Frontier 集，则所有操作都有 log(|v|)，结果是 O(|E|log|V| + |V|log|V|)，但由于假设是合理的|E| > |V|，你有 O(|E|log|V|).
然后是 Fibonacci 堆，在这里你有 O(1) 最小 Insert/Update/Find 的摊销时间，但是 O(log|V|) 最小的 Delete 摊销时间，给你当前Dijkstra 算法 O(|E| + |V|log|V|) 的最佳已知时间范围。

最后，如果 (|V|log|V| < |E|)，解决 O(|V|log|V|) 最坏情况下时间复杂度的单源最短路径问题的算法是不可能的，因为该问题的下限时间很简单 [=28] =] 即您需要至少检查每个顶点和边一次才能解决问题。

Dijkstra 算法的复杂性

Complexity Of Dijkstra's algorithm

c++

algorithm

dijkstra

time-complexity

shortest-path