3
我從很多來源讀到，如果使用簡單的方法來獲得最小元素（線性搜索），Dijkstra的最短路徑也將以O（V^2）複雜度運行。但是，如果使用優先級隊列，則可優化爲O（VLogV），因爲此數據結構將在O（1）時間內返回最小元素，但在刪除最小元素後需要O（LogV）時間來恢復堆屬性。Dijkstra算法的複雜性
我已經實現的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個鄰居？由於每個頂點必須在每一輪看V-1，V-2，V-3 ...節點，它不會使Dijkstra算法在O（V^2）中運行嗎？
再次想到，我可能誤解了最壞的情況下的複雜性。有人可以請在下列問題上給我提供建議：
- Dijkstra的算法O（VLogV）是如何特別給出上述反例的？
- 我怎樣才能優化我的代碼，以便它可以實現O（VLogV）複雜性（或更好）？
編輯：
我意識到，我的程序不會在O（ElogV）畢竟運行。瓶頸是由我在O（V^2）中運行的輸入處理引起的。 dijkstra部分確實在（ElogV）中運行。