图论算法--单源最短路--dijkstra算法（优先队列优化）

1.算法描述与分析：

（1、）解决的问题：求源节点 s 到其他节点的最短路，适合权值为正，且不含环的图。

（2、）算法描述与实现：这里直接描述优先队列的dijkstra算法实现，该算法的实现和图的BFS搜最短路的算法类似，都是从根节点

（源节点）开始搜索，遍历根节点的相邻节点，我们记源节点 s 到某节点 v 的最短距离是d[v]，第一步就是遍历所有的节点，这个时

候，我们需要一个优先队列，保证出队的值都是最小的，而且不重复的，（即：与父节点有最短路径而且该节点还未被访问过，或者

说是最短路径还没有被搜索过）首先是初始化的过程，我们需要一个存储源节点 s 到某节点 u 最短路径的数组 d，有些题目中需要打

印最短路径，因此也需要一个存储最短路生成树某节点父节点的数组 p ，我们可以不用设置一个标记数组，而是在设置节点数据类型

的时候，直接进行限制，保证出队的节点的最短路径一定是不相等的，这样不仅避免了重复访问的问题，而且也避免了相同路径都访

问的问题。初始化后，我们把源节点 s 入队。然后进行循环，直到队列为空，每次都取优先队列的第一个元素，（最小值先出队），

然后找到源节点 s 到节点 u 的最短路径，并且更新最短路径，然后将该节点的父节点赋给数组 p, 再将节点u 入队，循环直到队列为

空。

（3、）伪代码实现：

第一步：先建立节点，节点的内容：最短路d,和节点编号u,

第二补：初始化

第三步：源节点入队。

第四步：循环，不断的更新d,不断的入队，出队。

（4、）代码实现：

#include <bits/stdc++.h>
using namespace std;

const int maxn=1000+10;
const int INF=1<<27;
struct node
{
    int d,u;
    node(int a=0,b=0):d(a),u(b){}
    bool operator<(const node &a)const
    {
        if(d==a.d)
            return u<a.u;
        else
            return d>a.d;
    }
};
vector <node> G[maxn];
int d[maxn];
int pi[maxn];
int n;
void dijkstra(int s)
{
    priority_queue <node>q;
    for(int i=0;i<n;i++)
        d[i]=INF;
    d[s]=0;
    q.push_back(node(0,s));
    while(!q.empty())
    {
        node x=q.top();
        q.pop();
        int u=x.u;
        for(int i=0;i<G[u].size();i++)
        {
             node e=G[u][i];
             if(d[e.u]>d[u]+e.d)
             {
                 d[e.u]=x.d+e.d;
                 pi[e.u]=u;
                 q.push_bacK(node(d[e.u],e.u));
             }
        }
    }
}

小结：dijkstra算法和BFS赵最短路算法相似，可以对比。