dijkstra 的优先队列优化

　　既然要学习算法，就要学习到它的精髓，才能够使用起来得心应手。

　　我还是远远不够啊。

　　早就知道，dijkstra 算法可以用优先队列优化，我却一直不知道该怎样优化。当时，我的思路是这样的：假设有n个顶点，将这n个顶点的id和距原点的距离放在结构体内，再将这n个结构体放入优先队列中，堆顶是距源点距离最小的点。每次要更新距离时，仅仅只需要取堆顶的数就可以了。然而，具体要怎样更新堆内各点的距离呢？将堆顶取出，更新后再放回去？这样的话堆顶永远都会是同一个元素了，因为堆顶元素在更新后，还是距离最小的。那么我们可以依次取出堆顶元素，放在结构体数组之内，等待更新完毕后再放回去，那么这样的时间复杂度是2*n,而原先的时间复杂度，也是2*n，这样的优化没有意义，反而还多了一个结构体数组浪费空间。

　　如果你也和我的想法一样，那我们真是太有缘分了，看来大家都是蠢的七窍流血的一类人啊，你是不是也和我一样，正在反思自己是不是应该放弃学习算法啊？实际上，在dijkstra里面，有一个十分重要的标记数组，这个标记数组决定了，已经确定了最短距离的点，就不要再次优化了！你明白了吧，想想自己真是蠢呐，竟然忘记如此重要的数组！

　　让我们再次思考，是否要将所有没有确定的点全部放入数组呢？

　　当然不要，我们只要将刚刚更新过的放进去就行，因为那些没有更新的，肯定不会是路径最短的。那么我们每次都放，就会导致某个节点被放进去很多次了，但是没关系，他们的被放进去的时候，距离是不同的，所以距离大的会沉到底下去，最短路径一定不是他们（对同一节点来说），他们要出推时，我们只处理第一个，以后的一律不处理。这个我们还用一个标记数组来解决。

　　代码自己去找吧，https://blog.csdn.net/jobsandczj/article/details/49962557，这个人写得不错，除了码风很丑，加上竟然使用邻接矩阵。。。然后还有book数组定义了没有使用以外，其他的都还行。

　　如果你连这些问题都不想面对，或者根本就不想看代码的话，你还是转行吧。

 　　在此还是贴上自己的模板吧

　　这个模板跑起来反而比我原先的代码更慢，我觉得这是邻接表的问题，因为在一开始我用的是啊哈算法的邻接表，而现在用的是vector，再加上可能我在做的那个题太水了，数据量太小，导致优先队列的优势没有发挥出来。

#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; }

　　

 下面的代码包括了对路径的输出，只是我没有找到这样的题，所以不敢保证算法的正确性：

#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; }

　　

　　每个人都是被动出生，只有选择死亡才是真正的自由！

转载于:https://www.cnblogs.com/ZGQblogs/p/9010940.html

总结

以上是生活随笔为你收集整理的dijkstra 的优先队列优化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。