速度是沒有極限的。
衆說周知，Dijikstra是一種最短路算法，複雜度為O(V^2+E)
樸素Dijikstra
void Dijikstra(int s){
memset(dis,inf,sizeof(dis));
dis[s]=;
for(int i=;i<=n;++i){
int maxs=inf,u=;
for(int j=;j<=n;++j)
if(!vis[j]&&dis[j]<maxs)
maxs=dis[j],u=j;
vis[u]=;
for(int e=pre[u];e;e=nx[e]){
const int v=to[e];
if(dis[v]>dis[u]+w[e])
dis[v]=dis[u]+w[e];
}
}
}
其實對于稠密圖它還是很棒了。 但我們不滿足于此。
常見優化-heap優化
這裡我們采用STL_priority_queue進行優化
typedef pair<int,int> p;
priority_queue<p,vector<p>,greater<p> > q;
void Dijikstra(int s){
memset(dis,inf,sizeof(dis));
dis[s]=;
q.push(p(,s));
while(!q.empty()){
const int u=q.top().second;
q.pop();
if(!vis[u]){
vis[u]=;
for(int e=pre[u];e;e=nx[e]){
const int v=to[e];
if(!vis[v]&&dis[v]>dis[u]+w[e])
dis[v]=dis[u]+w[e],
q.push(p(dis[v],v));
}
}
}
}
這樣的話複雜度就到了O((V+E)logV) 但是，常數大。 手寫堆比較複雜，不現實。
奇怪的優化-線段樹優化
這并不是自己發現的，但是網上資料少就記錄一下吧。 我們回頭看看樸素的Dijikstra以及priority_queue優化。 發現優化的主要思路就是減少了查詢目前dis最小點的複雜度。 那麼也很容易想到用線段樹來維護dis的最小值吧。 這樣問題就變成了 整體最小值與單點修改，很簡單的線段樹操作吧。
int tree[N<<],leaf;
/*線段樹存的是點的标号*/
int check(int i,int j){
return dis[i]<dis[j]?i:j;
}
void build(){
memset(dis,inf,sizeof(dis));
for(leaf=;leaf<=n;leaf<<=);--leaf;
for(int i=;i<=n;++i) tree[leaf+i]=i;
}
/*修改 dis[x] 為 y*/
void change(int x,int y){
dis[x]=y,x+=leaf,x>>=;
while(x) tree[x]=check(tree[x<<],tree[x<<|]),x>>=;
}
void Dijikstra(int s){
build();
dis[s]=;
int u=s;
for(int i=;i<=n;++i){
ans[u]=dis[u];
change(u,max_int); /*删除u*/
for(int e=pre[u];e;e=nx[e]){
const int v=to[e];
if(dis[v]>ans[u]+w[e])
change(v,ans[u]+w[e]);
}
u=tree[];
}
}
這個比堆短吧。 而且非遞歸的線段樹常數也很小呢。
測試&總結
以luogu的單源最短路模闆題(稀疏圖,無O2)作為測試。
- 樸素的Dijikstra 2000+ms
- Dijikstra+priority_queue 652ms
- Dijikstra+線段樹 192ms 然後加11了SLF和LLL的SPFA也很快，大概300ms
是以SPFA和Dijikstra+priority_queue是很實用的，但如果想卡排名的話可以試一試線段樹啊
—來自xb神犇