Dijkstra算法的复杂性

Question

我从许多来源读到,如果使用一种天真的方式来获得最小元素(线性搜索),Dijkstra的最短路径也将以O(V ^ 2)复杂度运行.但是,如果使用优先级队列,它可以优化为O(VLogV),因为此数据结构将在O(1)时间内返回min元素,但在删除min元素后需要O(LogV)时间来恢复堆属性.

我已经在以下代码中通过以下代码实现了Dijkstra的算法:https://uva.onlinejudge.org/index.php？option = com_onlinejudge&Itemid = 8&category = 16&page = show_problem&issue_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)中运行.

Answer 1

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

• 插入
• 更新
• 查找/删除最小值

有O(|V|)插入,O(|E|)更新,O(|V|)查找/删除总对算法的整个过程中的数据结构中出现的最小值.

• 最初Dijkstra使用未排序的数组实现了Frontier集.因此,它O(1)适用于插入和更新,但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)分配插入/更新/查找最小值的O(log|V|)时间,但是删除最小值的分摊时间,给你目前最知名的O(|E| + |V|log|V|)Dijkstra算法的时间界限.

最后,O(|V|log|V|)如果(|V|log|V| < |E|)由于问题具有平凡的较低时间界限,O(|E| + |V|)即你需要至少检查一次顶点和边缘以解决问题,则不可能在最坏情况时间复杂度下解决单源最短路径问题的算法.