既然要學(xué)習(xí)算法，就要學(xué)習(xí)到它的精髓，才能夠使用起來得心應(yīng)手。

　　我還是遠(yuǎn)遠(yuǎn)不夠啊。

　　早就知道，dijkstra 算法可以用優(yōu)先隊(duì)列優(yōu)化，我卻一直不知道該怎樣優(yōu)化。當(dāng)時(shí)，我的思路是這樣的：假設(shè)有n個(gè)頂點(diǎn)，將這n個(gè)頂點(diǎn)的id和距原點(diǎn)的距離放在結(jié)構(gòu)體內(nèi)，再將這n個(gè)結(jié)構(gòu)體放入優(yōu)先隊(duì)列中，堆頂是距源點(diǎn)距離最小的點(diǎn)。每次要更新距離時(shí)，僅僅只需要取堆頂?shù)臄?shù)就可以了。然而，具體要怎樣更新堆內(nèi)各點(diǎn)的距離呢？將堆頂取出，更新后再放回去？這樣的話堆頂永遠(yuǎn)都會(huì)是同一個(gè)元素了，因?yàn)槎秧斣卦诟潞?#xff0c;還是距離最小的。那么我們可以依次取出堆頂元素，放在結(jié)構(gòu)體數(shù)組之內(nèi)，等待更新完畢后再放回去，那么這樣的時(shí)間復(fù)雜度是2*n,而原先的時(shí)間復(fù)雜度，也是2*n，這樣的優(yōu)化沒有意義，反而還多了一個(gè)結(jié)構(gòu)體數(shù)組浪費(fèi)空間。

　　如果你也和我的想法一樣，那我們真是太有緣分了，看來大家都是蠢的七竅流血的一類人啊，你是不是也和我一樣，正在反思自己是不是應(yīng)該放棄學(xué)習(xí)算法啊？實(shí)際上，在dijkstra里面，有一個(gè)十分重要的標(biāo)記數(shù)組，這個(gè)標(biāo)記數(shù)組決定了，已經(jīng)確定了最短距離的點(diǎn)，就不要再次優(yōu)化了！你明白了吧，想想自己真是蠢吶，竟然忘記如此重要的數(shù)組！

　　讓我們?cè)俅嗡伎?#xff0c;是否要將所有沒有確定的點(diǎn)全部放入數(shù)組呢？

　　當(dāng)然不要，我們只要將剛剛更新過的放進(jìn)去就行，因?yàn)槟切]有更新的，肯定不會(huì)是路徑最短的。那么我們每次都放，就會(huì)導(dǎo)致某個(gè)節(jié)點(diǎn)被放進(jìn)去很多次了，但是沒關(guān)系，他們的被放進(jìn)去的時(shí)候，距離是不同的，所以距離大的會(huì)沉到底下去，最短路徑一定不是他們（對(duì)同一節(jié)點(diǎn)來說），他們要出推時(shí)，我們只處理第一個(gè)，以后的一律不處理。這個(gè)我們還用一個(gè)標(biāo)記數(shù)組來解決。

　　代碼自己去找吧，https://blog.csdn.net/jobsandczj/article/details/49962557，這個(gè)人寫得不錯(cuò)，除了碼風(fēng)很丑，加上竟然使用鄰接矩陣。。。然后還有book數(shù)組定義了沒有使用以外，其他的都還行。

　　如果你連這些問題都不想面對(duì)，或者根本就不想看代碼的話，你還是轉(zhuǎn)行吧。

?　　在此還是貼上自己的模板吧

　　這個(gè)模板跑起來反而比我原先的代碼更慢，我覺得這是鄰接表的問題，因?yàn)樵谝婚_始我用的是啊哈算法的鄰接表，而現(xiàn)在用的是vector，再加上可能我在做的那個(gè)題太水了，數(shù)據(jù)量太小，導(dǎo)致優(yōu)先隊(duì)列的優(yōu)勢(shì)沒有發(fā)揮出來。

#include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; struct node {int x;int s;bool operator<(const node p)const{return p.s<s;} }; bool book[100]; int dis[100]; const int inf = 2100000000; int main() {vector<int>u[100];vector<int>w[100];int n,m;cin>>n>>m;int x,y,z;for(int i=0;i<m;i++){cin>>x>>y>>z;u[x].push_back(y);w[x].push_back(z);}fill(dis,dis+n+1,inf);dis[1]=0;priority_queue<node>q;node exa;exa.x=1;exa.s=0;q.push(exa);while(!q.empty()){exa=q.top();q.pop();if(book[exa.x]){continue;}book[exa.x]=true;int t=exa.x;for(int i=0;i<u[t].size();i++){if(dis[u[t][i]]>dis[t]+w[t][i]){dis[u[t][i]]=dis[t]+w[t][i];exa.s=dis[u[t][i]];exa.x=u[t][i];q.push(exa);}}}for(int i=1;i<=n;i++){cout<<dis[i]<<" ";}cout<<endl; }

　　

?下面的代碼包括了對(duì)路徑的輸出，只是我沒有找到這樣的題，所以不敢保證算法的正確性：

#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<stack> using namespace std; struct node {int x;int s;bool operator<(const node p)const{return p.s<s;} }; bool book[100]; int dis[100]; int f[1000]; const int inf = 2100000000; int main() {vector<int>u[100];vector<int>w[100];int n,m;cin>>n>>m;int x,y,z;for(int i=0;i<m;i++){cin>>x>>y>>z;u[x].push_back(y);w[x].push_back(z);}fill(dis,dis+n+1,inf);fill(f,f+n+1,-1);dis[1]=0;priority_queue<node>q;node exa;exa.x=1;exa.s=0;q.push(exa);while(!q.empty()){exa=q.top();q.pop();if(book[exa.x]){continue;}book[exa.x]=true;int t=exa.x;for(int i=0;i<u[t].size();i++){if(dis[u[t][i]]>dis[t]+w[t][i]){dis[u[t][i]]=dis[t]+w[t][i];exa.s=dis[u[t][i]];f[u[t][i]]=t;exa.x=u[t][i];q.push(exa);}}}stack<int>h;for(int i=1;i<=n;i++){cout<<dis[i]<<": ";int ah=f[i];while(ah!=-1){h.push(ah);ah=f[ah];}while(!h.empty()){cout<<h.top()<<" ";h.pop();}cout<<i<<" ";cout<<endl;}cout<<endl; }

　　

　　每個(gè)人都是被動(dòng)出生，只有選擇死亡才是真正的自由！

轉(zhuǎn)載于:https://www.cnblogs.com/ZGQblogs/p/9010940.html

總結(jié)

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

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