?分析：

可知Dijkstra算法的復雜度是O(n*n)

Dijkstra算法在尋找集合T中距離最小的頂點W（即尋找dist數(shù)組中最小值）復雜度是O(n),在更新距離操作時復雜度為O(n)。

上述操作需要進行n次，將n個點的最短路徑值確定因此復雜度為O（n）?？梢园l(fā)現(xiàn)外層的n次循環(huán)是不可避免的，因為需要求出源點到各個點的最短路徑?？梢詢?yōu)化的地方就在尋找dist數(shù)組最小值。

可以采用合適的數(shù)據(jù)結構優(yōu)化該過程，這里采用了小根堆。小根堆查找最小值時復雜度為O(1)，更新里面的值時復雜度為O(logn).最后可將Dijkstra復雜度降至O(nlogn).

這里使用C++ ?STL中的priority_queue實現(xiàn)小根堆的操作，因為priority_queue默認是大根堆，因此需要重載小于運算符，變成小根堆

模板:

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=1e5+5; int n,m;struct qnode{int v,dis;qnode(int v=0,int dis=0):v(v),dis(dis) {}//起點，最短值 bool operator<(const qnode &r)const{return dis>r.dis;} }; struct Edge{int v,w;Edge(int v=0,int w=0):v(v),w(w) {} //鄰接點，權值 }; vector<Edge> ve[maxn]; int d[maxn]; bool vis[maxn];void addEdge(int u,int v,int w) {ve[u].push_back(Edge(v,w)); } void dijkstra(int start) {mem(vis,false);mem(d,inf);priority_queue<qnode> q;d[start]=0;q.push(qnode(start,0));//從起點開始 qnode tmp;while(!q.empty()){tmp = q.top();q.pop();int u=tmp.v;if(vis[u])continue;vis[u]=true;for(int i=0; i<ve[u].size(); i++){int v=ve[u][i].v;int w=ve[u][i].w;if(!vis[v]&&d[v]>d[u]+w){d[v]=d[u]+w;q.push(qnode(v,d[v]));}}} } int main() {while(~scanf("%d%d",&n,&m),n){for(int i=1; i<=n; i++)ve[i].clear();for(int i=0; i<m; i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);//建邊 addEdge(v,u,w);}dijkstra(1);printf("%d\n",d[n]);}return 0; }

?

總結

以上是生活随笔為你收集整理的dijkstra+堆优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。