写在前面：我是一只蒟蒻。
今天，我们来学习一下图论中很基础的一个问题，当然，它也可以很难。。。。。。
在正式的讲解最短路之前，我们来聊一聊存图方式。
对于一张有向图，我们一般由邻接矩阵和邻接表两种方式进行存储。对于无向图，可以把无向边看做两条方向相反的有向边，从而采用与有向图相同的存储方式，所以一下讲解最短路时，就以有向图为基准来进行讲解。
邻接矩阵，这是一个十分简单的存图方式，使用二维数组进行存储，但是空间复杂度O（n2）是十分不优秀的。很容易就“爆”了。
所以，我们就使用邻接表的方法进行存图。
具体如何存，下面是代码：
1 struct node{ 2 int to,next,w; 3 }e[2*MAXN]; 4 int cnt=0,head[MAXN]; 5 void add(int u,int v,int w){ 6 cnt++; 7 e[cnt].next=head[u]; 8 e[cnt].to=v; 9 e[cnt].w=w; 10 head[u]=cnt; 11 }
使用的时候我们就可以通过head【】来进行
1 for(int i=head[x];i;i=e[i].next){ 2 int y=e[i].to; 3 ......//进行一系列的操作 4 }
好的，前面我们就说到这里，下面进入正题
单源最短路
单源最短路问题（SSSP问题）
是说，给定一张有向图G=（V,E），V是点集，E是边集，即有n个点，m条边。节点[1,n]之间的连续整数编号，（x,y,z）表示从x指向y，长度为z的边。
设1号点为起点，求长度为n的数组dis【】，dis【i】表示从1到i的最短路径长度。
Dijkstra 算法
主要流程：
1、初始化dis【1】=0，其余节点的dis值为正无穷。
2、找到一个未标记的dis【x】最小的节点x，然后标记节点x。
3、扫描节点x的所有出边（x,y,z），如果dis【y】>dis【x】+ z，则使用dis【x】+ z来更新dis【y】。
4、重复2,3，直到所有节点都被标记。
代码（非堆优化）：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,dis[1005],vis[1005],a[1005][1005]; 4 void dj(){ 5 memset(dis,0x3f3f,sizeof(dis));//dis数组，存储距离 6 memset(vis,0,sizeof(vis));//标记是否访问过 7 dis[1]=0; 8 for(int i=1;i<n;i++){//重复n-1次 9 int x=0; 10 for(int j=1;j<=n;j++){ 11 if(!vis[j]&&(x==0||dis[j]<dis[x])){ 12 x=j;//寻找未标记节点中dis最小的并用全局最小值x更新其他节点 13 } 14 vis[x]=1; 15 } 16 for(int y=1;y<=n;y++){ 17 dis[y]=min(dis[y],dis[x]+a[x][y]); 18 } 19 } 20 } 21 int main(){ 22 scanf("%d%d",&n,&m); 23 memset(a,0x3f3f,sizeof(a)); 24 for(int i=1;i<=n;i++){ 25 for(int j=1;j<=m;j++){ 26 int b,c,d; 27 scanf("%d%d%d",&b,&c,&d); 28 a[b][c]=min(a[b][c],d);//矩阵存图 29 } 30 } 31 dj(); 32 for(int i=1;i<=n;i++){ 33 printf("%d",dis[i]); 34 } 35 return 0; 36 }
其主要思想是基于贪心的思想，仅适用于无负边权的图，我们不断选择我全局最小值进行标记和扩展更新，最终得到最短路长度。
不难看出，这个算法的时间复杂度为O（n2）十分之高，所以我们尝试进行优化（先留一个坑~~）
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010,M=1000010; 4 struct edge{ 5 int to,next,w; 6 }e[N]; 7 int head[N]; 8 bool vis[N]; 9 int dis[N]; 10 int n,m,tot; 11 priority_queue<pair <int ,int > >q; 12 void add(int x,int y,int z){ 13 e[++tot].next=head[x]; 14 e[tot].to=y; 15 e[tot].w=z; 16 head[x]=tot; 17 } 18 void dijkstra(){ 19 memset(dis,0x3f,sizeof(dis)); 20 memset(vis,0,sizeof(vis)); 21 dis[1]=0; 22 q.push(make_pair(0,1)); 23 while(q.size()){ 24 int x=q.top().second;q.pop(); 25 if(vis[x])continue; 26 vis[x]=1; 27 for(int i=head[x];i;i=e[i].next){ 28 int y=e[i].to,z=e[i].w; 29 if(dis[y]>dis[x]+z){ 30 dis[y]=dis[x]+z; 31 q.push(make_pair(-dis[y],y)); 32 } 33 } 34 } 35 } 36 int main(){ 37 scanf("%d%d",&n,&m); 38 for(int i=1;i<=m;i++){ 39 int x,y,z; 40 scanf("%d%d%d",&x,&y,&z); 41 add(x,y,z); 42 } 43 dijkstra(); 44 for(int i=1;i<=n;i++){ 45 printf("%d\n",dis[i]); 46 } 47 return 0; 48 }
OK，dj结束~^_^~
Bellman-Ford&&SPFA算法
给定一张有向图，若对于图中的某一条边（x,y,z），有dis【y】<=dis【x】+z成立，则称改该边满足三角形不等式。若所有边都满足三角形不等式，则dis数组就是所求最短路。
首先，我们先介绍一下基于迭代思想的算法bellman-ford。（尽管我不会，也不懂什么是迭代）
流程如下：（时间复杂度O（nm））
1、扫描所有边（x,y,z），若dis[y]>dis[x]+z，则进行更新。
2、一直重复，直到没有更新发生
SPFA算法，在国际上通称为“队列优化的bellman-ford算法”。
流程：
1、建立一个队列，最初的队列中只含有起点1。
2、取出队头节点x，扫描它的所有出边（x,y,z）（链式前向星）如果dis[y]>dis[x]+z,则更新dis[y]。同时判断y是否在队列中，如果不在，则将y加入队列。
3、重复操作，直到队列为空。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010,M=1000010; 4 struct edge{ 5 int to,next,w; 6 }e[N]; 7 int head[N]; 8 bool vis[N]; 9 int dis[N]; 10 int n,m,tot; 11 queue<int >q; 12 void add(int x,int y,int z){ 13 e[++tot].next=head[x]; 14 e[tot].to=y; 15 e[tot].w=z; 16 head[x]=tot; 17 } 18 void spfa(){ 19 memset(dis,0x3f,sizeof(dis)); 20 memset(vis,0,sizeof(vis)); 21 dis[1]=0,vis[1]=1; 22 q.push(1); 23 while(!q.empty()){ 24 int x=q.front();q.pop(); 25 vis[x]=1; 26 for(int i=head[x];i;i=e[i].next){ 27 int y=e[i].to,z=e[i].w; 28 if(dis[y]>dis[x]+z){ 29 dis[y]=dis[x]+z; 30 if(!vis[y])q.push(y),vis[y]=1; 31 } 32 } 33 } 34 } 35 int main(){ 36 scanf("%d%d",&n,&m); 37 for(int i=1;i<=m;i++){ 38 int x,y,z; 39 scanf("%d%d%d",&x,&y,&z); 40 add(x,y,z); 41 } 42 spfa(); 43 for(int i=1;i<=n;i++){ 44 printf("%d\n",dis[i]); 45 } 46 return 0; 47 }
相对于dj来说，spfa可以解决负边权的问题，其时间复杂度也是比较玄学的O（km），有时对于特殊的数据就会变为O（nm），所以spfa有风险，使用需谨慎。
now，The end of spfa。
Floyd 算法
flord算法的核心思想就是动态规划，最外层的k表示的是阶段，i，j为附加状态，所以应置于内层循环，然后状态转移方程就是d[i][j]=min(d[i][j],d[i][k]+d[k][j])
最终d[i][j]保存了i到j的最短路
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int d[310][310],n,m; 4 int main(){ 5 scanf("%d%d",&n,&m); 6 memset(d,0x3f3f,sizeof(d)); 7 for(int i=1;i<=n;i++)d[i][i]=0; 8 for(int i=1;i<=m;i++){ 9 int x,y,z; 10 scanf("%d%d%d",&x,&y,&z); 11 d[x][y]=min(d[x][y],z); 12 } 13 for(int k=1;k<=n;k++){ 14 for(int i=1;i<=n;i++){ 15 for(int j=1;j<=n;j++){ 16 d[i][j]=min(d[i][j],d[i][k]+d[k][j]); 17 } 18 } 19 } 20 for(int i=1;i<=n;i++){ 21 for(int j=1;j<=n;j++){ 22 printf("%d ",d[i][j]); 23 } 24 printf(" "); 25 } 26 return 0; 27 }
下面flord的传递闭包问题：（未完待续）。。。
原文：https://www.cnblogs.com/xishirujin/p/10414898.html