Dijkstra 入门

对于图论中最短路径的三种算法，我们可以总结为以下表格（m为边数，n为点数）：

算法	时间复杂度	功能	局限性
Dijkstra	O(mlogm)	寻找单源最短路	边权为正
Floyd	O(m3)	寻找多源最短路	无
SPFA	O(mn)	寻找单源最短路	边权为负

各最短路算法比较

接下来让我们来康康如何实现Dijkstra算法。

康康就康康

Dijkstra是寻找单源最短路的算法，即指定一个起点的最小值。所以我们需要先规定起点的点的标号为s，而终点的标号为e。

接着，我们再设dis[i]表示从s到i的最短路。显然，dis[s]=0，因为起点到自己本身的距离就是0；而我们要求的就是dis[e]。

下面，让我们来构造一个真实的例子（注意，Dijkstra可以处理无向图也可以是有向图）。

我们假定从1出发，走到6。

显然，对于和1相邻的点，我们可以先推出$dis[1]=0$，$dis[3]=1$，$dis[5]=5$。类似地，对于每一个确定了$dis$的点，都可以继续推出与其相邻的点的$dis$值。

那么根据上面的图，确定了$dis[5]=5$后，$dis[6]=dis[5]+2=7$；确定了dis[3]后，$dis[5]=dis[3]+2=3$……等等，dis[5]的值又被更新了一次。这意味着，如果先推dis[5]的相邻的点的话，其后面的推到都是错误的，因为如果从dis[3]推到dis[5]，dis[5]的值仅为3，说明了从1走到5的最小值并不是直接走到5，而是走到3再走到5。由此可见，对于一个已经确定dis的点，应该将其所有相邻的点的期望dis按从小到大排。优先算出期望dis最小的点。于是我们就需要用到优先队列，对于每个相邻的点记录下期望dis值并塞入队列（期望dis值即当前算出的dis值：$dis[next]=dis[now]+val$）。设置优先队列中期望dis值小的在队首，然后从队首一个个取出再塞进新的点即可，有点类似于广度优先搜索。于是$dis[next]=min(dis[next], dis[now]+val)$。这么一来，dis的初始值应全部设为无穷大。但不要忘记vis[s]=0！

一处优化

对于上方例子中的点3和点5被更新的问题，在经过改进后，不难发现5会先被点3的距离为3更新，此时一定是最优解。所以我们可以对于dis[now]!=now.val的直接跳过。

#include
   <bits tdc++.h="">

using namespace std;
int n,m,s;
struct node{
    int a,val;
    bool operator < (node b) const{
        return val>b.val;
    }
};
vector
    
      G[100010];
priority_queue
     
       q;
int dis[100010];
int main(){
    cin>>n>>m>>s;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    q.push({s,0});
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    while(!q.empty()){
        node now=q.top();
        q.pop();
        if(now.val!=dis[now.a])continue;
        for(int i=0;i
      <g[now.a].size();i++){ node="" nxt="G[now.a][i];" if(dis[nxt.a]="">
       dis[now.a]+nxt.val){
                q.push({nxt.a,dis[now.a]+nxt.val});
                dis[nxt.a]=now.val+nxt.val;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<
       <dis[i]<<" ";="" }="" return="" 0;="" }<="" re="">

        

         

       </dis[i]<<">
      </g[now.a].size();i++){>
     
    
   </bits>