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

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

dijkstra 的优先队列优化

推荐阅读