最短路径算法简介

最短路径算法是在图中求两点（或多点）之间的最短路径，我们最常见的最短路径算法有四种：Bellman-ford、Dijkstra、SPFA、Floyd。

Bellman-ford算法可以用于有负边权的图，如果途图中有负环，算法也可以检验出来，时间复杂度为O(VE)。

Dijkstra算法只能用于边权为正的图中，时间复杂度为O(n^2)。

SPFA算法是Bellman-ford算法的优化算法，和Bellman-ford算法应用差不多，而且可以用邻接表和队列优化，时间复杂度为O(KE)，SPFA的时间复杂度有常数，有的比赛可能会卡常，所以建议求图上最短路的时候用Dijkstra算法。

Floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的最小环和最大环。时间复杂度O（n^3）。

这篇博客主要介绍Dijkstra算法

Dijkstra算法

Dijkstra算法是我求图上单元最短路最常用的方法，他可以求出从图上一个点到其他所有点的最短路径，他可以用优先队列（堆）优化，我们先来介绍一下Dijkstra算法不优化的做法。

Dijkstra算法（不优化）

大体思路：先遍历一下还没有在最短路中的点，选出一个距离已经在最短路集合中的点距离最近的点，并把它加入到最短路中，并且更新所有点的最短路，直到所有的点都加入到最短路中。

下面我们来详细模拟一下Dijkstra算法的实现过程：

变量名：d[i]表示从起始点到节点i的最短路径 v[i]表示节点i是否被访问过

初始化：所有最短路赋值为+∞，并且使d[1]=0，v[1]=1，因为任何节点到它本身的距离为0，标记1被访问过。

我们来求一下下面这张图从①到其他节点的最短路径

步骤①：遍历与节点1相连的所有节点，找到距离最近的一个，把这个节点标记为访问过，并更新最短路。因为新加入一条边，可能有很多的最短路会发生改变，所以要更新所有与最短路径包含的点相连的点的最短路。由图可知，10>5>1，所以我们把节点4标记为访问过，v[4]=1，并且更新最短路——>d[4]=1。

步骤②：遍历与最短路包含的点相连的节点，找到距离最近的。2<5<10，所以把节点3加入最短路，并且标记为访问过—— d[3]=3,v[3]=1。

步骤③：遍历与最短路包含的点相连的节点，找到距离最近的。5<6<10，所以把节点2加入最短路，并且标记为访问过—— d[2]=5,v[2]=1。

步骤④：遍历与最短路包含的点相连的节点，找到距离最近的。6<10，所以把节点5加入最短路，并且标记为访问过—— d[5]=9,v[5]=1。

这样，这张图的最短路径就求出来了，是不是很好理解呢！

下面是代码

#include<iostream> #include<cstdio>
#define MAXN 2147483647
using namespace std; int n,m,s; struct G{ int u; int v; int w; int next; }e[500001]; int head[500001]; int d[500001]; int read(){ int num=0; char ch=getchar(); while(ch<'0' || ch>'9') ch=getchar(); while(ch>='0' && ch<='9'){ num=num*10+ch-'0'; ch=getchar(); } return num; } bool v[500001]; int main(){ int i,j; n=read(); m=read(); s=read(); for(i=1;i<=m;i++){ int a=read(),b=read(),c=read(); e[i].u=a; e[i].v=b; e[i].w=c; e[i].next=head[a]; head[a]=i; } for(i=1;i<=n;i++) d[i]=MAXN; //初始化
    d[s]=0; for(i=1;i<=n;i++){ int k=0,minn=MAXN; for(j=1;j<=n;j++) //寻找距离最小的点
          if(minn>d[j] && !v[j]){ minn=d[j]; k=j; } v[k]=1; //标记为访问过
        for(j=head[k];j!=0;j=e[j].next) if(!v[e[j].v] && d[e[j].v]>d[e[j].u]+e[j].w) //更新节点
            d[e[j].v]=d[e[j].u]+e[j].w; } for(i=1;i<=n;i++) cout<<d[i]<<" "; return 0; }

（存图的时候，建议用邻接表，方便，而且速度比数组快）

到此，我们最基础的Dijkstra算法就已经讲完了，下面我们来讲一下堆优化。

Dijkstra算法堆优化

堆优化用到了优先队列(priority_queue)，如果不会优先队列，可以先看一下这个博客学习一下 https://blog.csdn.net/c20182030/article/details/70757660。

我们来回顾一下算法的核心部分：先找最小距离，再更新。在不优化的时候，我们是每次通过循环来寻找最小距离的，这样的话就会有很多不必要的时间浪费掉，所以我们想到了用优先队列优化，因为优先队列会自动按照优先度排序，这样就会省掉寻找最小距离的循环，从而节省一部分时间。

然后我们再想一想优先队列里存放什么东西。我们来看一下不优化之前，在搜索最小距离的时候需要记录的东西——最小距离和节点的编号，所以我们在优先队列里面就放最小距离和节点的编号。为方便操作，我们就申请一个struct或者pair的优先队列，struct的话就申请两个变量，而pair的话（不了解pair的可以看一下这个博客 https://www.cnblogs.com/lvchaoshun/p/7769003.html），就在第一个位置里放距离，第二个位置里放id，因为优先队列默认先按照第一关键字排序，我们的目的就是要快速的找到最小距离，所以按照距离排序。优先队列默认从大到小排序，所以我们要使优先队列从小到大排序，或者是在加入新的二元组的时候，把距离变成负的。

其余的部分和不优化差别不是很大，下面给出代码：

#include<bits/stdc++.h>
using namespace std; typedef pair<int,int> pi; const int MAXN=2e6+10; struct EDGE{ int u; int v; int w; int next; }edge[MAXN]; int head[MAXN],tot; int t,ans; int n,m; char a[1000][1000]; int dis[MAXN]; bool vis[MAXN]; priority_queue<pi,vector<pi>,greater<pi> > q; pi tmp; int read(){ int x=0; char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9'){ x=x*10+c-'0'; c=getchar(); } return x; } void add(int x,int y,int z){ edge[++tot].u=x; edge[tot].v=y; edge[tot].w=z; edge[tot].next=head[x]; head[x]=tot; edge[++tot].u=y; edge[tot].v=x; edge[tot].w=z; edge[tot].next=head[y]; head[y]=tot; } int main(){ register int i,j; int id,x,nd; t=read(); while(t--){ for(i=1;i<=tot;i++) edge[i].next=edge[i].u=edge[i].v=edge[i].w=head[i]=0; tot=0; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); n=read(),m=read(); for(i=1;i<=n;++i) for(j=1;j<=m;++j){ cin>>a[i][j]; if(a[i][j]!='/') add((i-1)*(m+1)+j,i*(m+1)+j+1,0),add((i-1)*(m+1)+j+1,i*(m+1)+j,1); else  add((i-1)*(m+1)+j,i*(m+1)+j+1,1),add((i-1)*(m+1)+j+1,i*(m+1)+j,0); } if((m+n)%2!=0){ printf("NO SOLUTION\n"); continue; } q.push(make_pair(0,1)); while(!q.empty()){ tmp=q.top(); q.pop(); id=tmp.second,nd=tmp.first; if(vis[id]) continue; vis[id]=1; for(i=head[id];i;i=edge[i].next){ if(vis[edge[i].v]) continue; if(dis[edge[i].v]>nd+edge[i].w){ dis[edge[i].v]=nd+edge[i].w; q.push(make_pair(dis[edge[i].v],edge[i].v)); } } } printf("%d\n",dis[(n+1)*(m+1)]); } return 0; }

（洛谷原题链接https://www.luogu.org/problemnew/show/P2243）

（本博客部分内容摘自：https://blog.csdn.net/qq_36386435/article/details/77403223）