图论
嗯。
2018-09-17 20:04:57
# 1.关于图的基本概念
参考了：博客[emm](https://blog.csdn.net/saltriver/article/details/54428685)和 [emm](https://blog.csdn.net/qq_22238021/article/details/78276420) 以及严蔚敏的《数据结构》
## （1）~~瞎扯淡~~ 图：
图是一种较线性结构和树形结构更复杂的数据结构。线性结构中，每个元素之和一个直接前驱和一个直接后继;树形结构中，每个元素只和其父亲还有他的有关;而图中，任意两个元素都可能有关联。所以图是十分有用的但又是十分难的。
## （2）图的定义：
简单的说，图是一个用线或边连接在一起的顶点或节点的集合，严格的说，图是有限顶点V和边E的有序对。即G=(V,E)，V为顶点集，E为边集。设图有n个顶点，V={v1,v2,v3,......,vn}。~~鸟语听不懂~~
## （3）图的基本术语：
- 顶点：表示某个事物或对象,由于图中对其的术语没有标准化，因此称顶点为点、节点、结点、端点等都是可以的。
- 边：顶点之间的线条就是边，表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系，粗细长短都无所谓的。
- 有向图：边<u,v>属于E，表示从弧尾v到弧头w的一条弧。~~鸟语听不懂~~（就是图中的所有的边都是有方向的）。
- 无向图：边<u,v>属于E，则边<v,u>也属于E。~~鸟语还是听不懂~~（就是图中的所有的边都是双向的或者说是没有方向的）。
- 混合图：既有有向边，又有无向边的图。
- 简单无向图：不存在顶点到自身的边，且任意两个不同的顶点之间没有平行的两条边。
- 简单有向图：不存在顶点到自身的弧，且任意两个不同的顶点之间没有同方向的两条弧。
- 无向完全图：对简单无向图，图中任意两个不同的顶点间都有边，有n个顶点的无向完全图有n(n-1)/2条边。
- 有向完全图：对简单有向图，任意两个顶点间都有方向互为相反的两条弧。有n个顶点的有向完全图有n(n-1)条弧。
- 稀疏图：有很少条边或弧。
- 稠密图：有很多条边或弧。
- 简单图：简单无向图和简单有向图统称为简单图。(就是没有自己指向自己的边以及起点和终点都相同的边)。
- 邻接 依附 关联（无向图）：若无向图有边<u,v>，称顶点u和v相邻或邻接，称<u,v>依附点u和v,称与边<u,v>相关联的两个顶点是u和v。
- 邻接 依附 关联（有向图）：若有向图有弧<u,v>，称顶点u邻接到v，v邻接自u，弧<u,v>依附点u和v，称与弧<v,w>相关联的两个顶点是v和v，通常称v是u的邻接点。
- 权重（权，权值）：边或弧上和其有关的某种物理量。
- 网：边或弧上带权值的图。
- 度：和某个点相关联的边数称为这个点的度。（无向图中，所有顶点的度之和是边总数的2倍）。
- 入度：以某个点为弧头的弧的数目称为这个点的入度。
- 出度：以某个点为弧尾的弧的数目称为这个点的出度。（入度和出度只有有向图中才有，某个点的入度和出度之和等于度）
- 子图：G=(V,E),G'=(V',E')，若V'是V的子集，E'是E的子集，且E'中的边仅与V'中的顶点相关联，则G'是G的子图。
- 路径：G=(V,E)，若有顶点序列（vs=vi1,vi2,vi3,...,vik=vk）且边(vij-1,vij）属于E，称（vi1,vi2...vik）为vs到vk的路径。
- 回路（环）：第一个顶点和最后一个顶点相同的路径。
- 简单路径：序列中顶点不重复的路径。
- 连通和可达：有向图中顶点u到v有路径称u到v是可达的;无向图中u到v有路径称u和v是连通的。
- 连通图：无向图中任意两个不同顶点都是连通的称它为连通图，否则为非连通图。
- 强连通图：有向图中任意两个不同顶点都是可达的称之为强连通图或简称连通图，否则为非强连通图或非连通图。
- 连通分量：无向图的极大连通子图称为连通分量.
- 强连通分量:有向图的极大强连通子图称为强连通分量或连通分量。(极大指该子图包括了所有连通的顶点以及这些顶点相关联的所有边)
- 生成树:由n个顶点构成的连通无向图的任何一个含n个顶点的极小连通子图。
------------
# 2.图的存储结构
参考了：博客[emm](https://blog.csdn.net/zhembrace/article/details/72625413) 以及严蔚敏的《数据结构》
## （1）直接存 ~~不知道是什么方法~~
- 直接用三个一维数组u，v，w来存储边;u[i]表示第i条边的起点，v[i]表示第i条边的终点，w[i]表示第i条边的权值。每次直接暴力扫。
- 优点：方便，容易理解，空间复杂度还行。
- 缺点：遍历时，时间复杂度O（n×m）很高。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
int n,m,u[100001],v[100001],w[100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
cin>>u[i]>>v[i]>>w[i];
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
if(u[j]==i)
cout<<u[j]<<" "<<v[j]<<" "<<w[j]<<endl;
return 0;
}
```
## （2）邻接矩阵
- 用一个二维数组a来存储边;a[i][j]表示一条i到j的边的权值，如果无边相连则a[i][j]=INF。
- 顶点v的度是矩阵中第v行不为INF的元素数量之和。
- 优点：简洁，便于查询某两个点之间是否有边。
- 缺点：遍历时，时间复杂度O（n^2）很高。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
int n,m,u,v,w,a[1001][1001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
//应初始化数组为INF。
for(register int i=1;i<=m;i++)
{
cin>>u>>v>>w;
a[u][v]=w;
//如果是无向图还要加上a[v][u]=w;
}
for(register int i=1;i<=n;cout<<endl,i++)
for(register int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
return 0;
}
```
## （3）数组模拟邻接表（前向星）
参考了：博客[emm](http://developer.51cto.com/art/201404/435072.htm)
- 一般不直接用vector调用邻接表，用数组模拟的快一些 ~~其实是不会~~
- 用五个数组u，v，w，head，next。u[i]表示第i条边的起点,v[i]表示第i条边的终点,w[i]表示第i条边的权值,first[i]表示第i个点所有边中最后存入的那条边的编号,next[i]表示与第i条边同一起点的上一条边所对应的编号 ~~什么鬼 听不懂~~
- 那就上图
要存入的边：
初始状态：初始时first都是-1。
放入第一条边时：所以此时first[1]=1;
放入第二条边时：所以此时first[4]=2;
放入第三条边时：因为这条边的起点和第一条边的一样都是1,所以第3条边就将第一条边从first[1]挤下来，此时first[1]=3了，然后要将next[3]=1;
放入第四条边时：所以此时first[2]=4;
放入第五条边时：因为这条边的起点和第一和第三条边的一样都是1，所以第5条边就将第三条边从first[1]挤下来，此时first[1]=5了，然后要将next[5]=3;
- 通过这些图就能很好地理解怎么存的，那么遍历的时候，对于v点，取出first[v]，并赋给i;然后不断跳i=next[i];直到没有边可以跳。这样就能将所有以v为起点的边遍历完。 for(int i=head[v];i!=0;i=nex[i])直接用first和next会报错。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
using namespace std;
int n,m,u[100001],v[100001],w[100001],head[100001],nex[100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
cin>>u[i]>>v[i]>>w[i];
nex[i]=head[u[i]];
head[u[i]]=i;
}
for(register int i=1;i<=n;i++)
for(register int j=head[i];j;j=nex[j])//遍历以j为起点的边
cout<<u[j]<<" "<<v[j]<<" "<<w[j]<<endl;
return 0;
}
```
## （4）链式邻接表（结构体）
- 与数组模拟邻接表一样，只是是用一个结构体将几个数组存在一起了。直接上代码吧。
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct zhzs
{
int next;
int to;
int w;
}edge[100001];//可以不用存起点了
int n,m,x,y,z,k,head[100001];
inline void add(int u,int v,int w)
{
k++;
edge[k].w=w;
edge[k].to=v;
edge[k].next=head[u];
head[u]=k;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
//如果是无向图还要加add(y,x,z);
}
for(register int i=1;i<=n;i++)
for(register int j=head[i];j;j=edge[j].next)//遍历以j为起点的边
cout<<i<<" "<<edge[j].to<<" "<<edge[j].w<<endl;
return 0;
}
```
------------
# 3.图的遍历
参考了：博客[emm](https://blog.csdn.net/luoshixian099/article/details/51897538) 以及严蔚敏的《数据结构》
## （1）~~瞎扯淡~~ 定义及作用：
- 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这个过程就是图的遍历。
- 图的遍历是求解图的连通性问题 拓扑排序和求关键路径等算法的基础。
## （2）法1（dfs深度优先搜索）：
参考了：博客[emm](https://blog.csdn.net/jinzhao1993/article/details/51166850)
- 从图中某个顶点v出发，首先访问v;访问结点v的第一个邻接点，以这个邻接点vt作为一个新节点，访问vt所有邻接点。直到以vt出发的所有节点都被访问到，回溯到v的下一个未被访问过的邻接点，以这个邻结点为新节点，重复上述步骤，直到图中所有与v相通的所有节点都被访问到。若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点。重复该过程，直到图中的所有节点均被访问过。
- 用一个b数组记录该点是否被访问过。
邻接矩阵版：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,x,y,z,sum=0,a[1001][1001],b[1001];
void dfs(int u)//当前所在的起点编号
{
sum++;
if(sum==n)//全被遍历完了就可以结束了。
return;
for(register int i=1;i<=n;i++)
if(a[u][i]!=2139062143&&!b[i])
{
b[i]=1;
dfs(i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
memset(a,0x7f,sizeof(a));
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
a[x][y]=z;
}
for(register int i=1;i<=n;i++)
if(!b[i])
dfs(i);
return 0;
}
```
链式邻接表版：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct zhzs
{
int to;
int w;
int next;
}edge[100001];
int k,n,m,x,y,z,sum=0,b[100001],head[100001];
inline void add(int u,int v,int w)
{
edge[++k].to=v;
edge[k].w=w;
edge[k].next=head[u];
head[u]=k;
}
void dfs(int u)
{
sum++;
if(sum==n)
return;
for(register int i=head[u];i;i=edge[i].next)
if(!b[edge[i].to])
{
b[edge[i].to]=1;
dfs(i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
for(register int i=1;i<=n;i++)
if(!b[i])
dfs(i);
return 0;
}
```
## （3）法2（bfs广度优先搜索）：
参考了：博客[emm](https://blog.csdn.net/luoshixian099/article/details/51897538) 以及严蔚敏的《数据结构》
- 从图中某个顶点v出发，首先访问v，依次访问v的各个未被访问的邻接点，依次从上述邻接点出发，访问他们的各个未被访问的邻接点。始终保证一点：如果vi在vk之前被访问，则vi的邻接点应在vk的邻接点之前被访问。重复上述步骤，直到所有顶点都被访问到。如果还有顶点未被访问到，则随机选择一个作为起始点，重复上述过程，直到图中所有顶点都被访问到。
- 用队列来实现上面的要求
邻接表版：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> q;
int n,m,x,y,z,sum=0,a[1001][1001],b[1001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
memset(a,0x7f,sizeof(a));
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
a[x][y]=z;
}
q.push(1);
b[1]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(register int i=1;i<=n;i++)
{
if(!b[i]&&a[t][i]!=0x7f7f7f7f)
{
q.push(i);
b[i]=1;
sum++;
}
if(sum==n)
exit(0);
}
}
return 0;
}
```
链式邻接表版：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> q;
struct zhzs
{
int to;
int w;
int next;
}edge[100001];
int k,n,m,x,y,z,sum=0,b[100001],head[100001];
inline void add(int u,int v,int w)
{
edge[++k].to=v;
edge[k].w=w;
edge[k].next=head[u];
head[u]=k;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
q.push(1);
b[1]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(register int i=head[t];i;i=edge[i].next)
{
if(!b[edge[i].to])
{
sum++;
q.push(edge[i].to);
b[edge[i].to]=1;
}
if(sum==n)
exit(0);
}
}
return 0;
}
```
------------
# 4.有向无环图及其应用
参考了严蔚敏的《数据结构》
## （1）~~瞎扯淡~~ 定义：
- 一个无环的有向图称作有向无环图，简称DAG图
## （2）拓扑排序：
- 由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序： 1. 每个顶点出现且只出现一次； 2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径，即如果存在一条从顶点A到顶点B的路径(B依赖A)，那么在排序结果中A在B的前面。
```cpp
#include<bits/stdc++.h>
using namespace std;
int u[10000],v[10000],h[10000],ne[10000],p[10000],d[10000],l[10000];
int main(){
int n,m;
cin>>n>>m;
for(int q=1;q<=m;q++){
cin>>u[q]>>v[q];
ne[q]=h[u[q]],h[u[q]]=q;
p[v[q]]++;
}
int i=1;
for(int q=1;q<=n;q++)
if(p[q]==0){d[i]=q,i++,l[q]=1;cout<<q<<" ";break;}
for(int q=1;q<=i;q++)
for(int w=h[d[q]];w;w=ne[w])
if(!l[v[w]]){
p[v[w]]--;
if(!p[v[w]]){cout<<v[w]<<" ";l[v[w]]=1,d[i]=v[w],i++;}
}
}
```
## （３）：题目：
- [旅行计划](https://www.luogu.org/problemnew/show/P1137) 拓扑排序＋递推
-
------------
# 5.最小生成树
参考了博客[emm](https://blog.csdn.net/qq_35644234/article/details/59106779) 以及严蔚敏的《数据结构》和《全国青少年信息学竞赛培训教材（复赛篇）》
## （1）~~瞎扯淡~~ 定义：
- 现在假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
- 于是我们就可以引入连通图来解决我们遇到的问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
- 构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设G=(V,E)是一个连通网，U是顶点集V的一个非空子集，如果<u，v>是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用MST性质生成最小生成树的算法：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
## （2）法1（Prim算法）：
- 算法思路：Prim算法是一种贪心算法，方法为从任意顶点v开始构造生成树，首先将v加入生成树tree中，然后用dis[j]数组记录其他顶点到v的距离，有边相连时，距离值为w<v，j>;无边相连时，距离值为inf。扫描一维数组dis[j]，选取值最小的顶点j加入tree，并将相应的边也加入tree中。再以j为中间点，更新上面的操作，直到tree中有n个顶点。
- 实现起来有邻接矩阵和邻接表两种方法。为了方便之后都只写链式邻接表的算法。算法思路上代码更容易理解一些
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct zhzs
{
int to;
int next;
int w;
}edge[1000001];
int n,m,x,k,y,z,b[200001],head[200001],t;
long long dis[200001],minn=1e9+1,ans;
inline void add(int u,int v,int w)
{
edge[++k].to=v;
edge[k].w=w;
edge[k].next=head[u];
head[u]=k;
}//链式邻接表
inline int min(long a1,long b1)
{return a1<b1?a1:b1;}//重载取小函数，更快
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
fill(dis+1,dis+n+1,1e9+1);
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
b[1]=1;
for(register int i=head[1];i;i=edge[i].next)
dis[edge[i].to]=edge[i].w;
dis[1]=0;
for(register int i=1;i<=n-1;i++)
{
minn=1e9;
for(register int j=1;j<=n;j++)
if(!b[j]&&minn>dis[j])
{
minn=dis[j];
t=j;
}//每次取出最小的边，用MST性质
b[t]=1;
for(register int j=head[t];j;j=edge[j].next)
if(!b[edge[j].to])
dis[edge[j].to]=min(dis[edge[j].to],edge[j].w);
}
for(register int i=1;i<=n;i++)
ans+=dis[i];
cout<<ans;
return 0;
}
```
堆优化版：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
struct zhzs
{
int to;
int next;
long long w;
}edge[1000001];
int n,m,x,k,y,z,sum,b[200001],head[200001];
long long dis[200001],minn=1e9+1,ans;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
//优先队列模拟推，采用双关键字排序
inline void add(int u,int v,long long w)
{
edge[++k].to=v;
edge[k].w=w;
edge[k].next=head[u];
head[u]=k;
}
inline int min(long a1,long b1)
{return a1<b1?a1:b1;}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;suanfa
fill(dis+1,dis+n+1,1e9+1);
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
q.push(make_pair(0,1));
dis[1]=0;
while(q.size())
{
int t=q.top().second;
q.pop();
if(!b[t])
{
ans+=dis[t];
b[t]=1;
for(register int i=head[t];i;i=edge[i].next)
{
dis[edge[i].to]=min(dis[edge[i].to],edge[i].w);
q.push(make_pair(dis[edge[i].to],edge[i].to));
}
}
}
cout<<ans;
return 0;
}
```
## （3）法2（Kruskal算法）：
- 算法思路：Kruskal算法是另一种贪心算法，它是将边按权值排序，每次从剩下的边集中选取权值最小且两个端点不在同一个集合的边加入tree中，反复操作，知道加入了n-1条边。
- 实现：对边排序就将边按结构体存下，然后用sort的结构体排序实现，判断端点是否在同一个集合就用并查集实现。直接上代码来理解吧
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,baba[200001];
long long ans;
struct hbbzs
{
int u,v;
long long w;
}edge[1000001];
inline bool zhzs(hbbzs x,hbbzs y)
{return x.w<y.w;}
inline int find(int t)
{return baba[t]==t?t:baba[t]=find(baba[t]);}//并查集找爸爸操作
inline void he(int x,int y)//合并操作
{
int x1=find(x),y1=find(y);
baba[y1]=baba[x1];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
cin>>edge[i].u>>edge[i].v>>edge[i].w;
sort(edge+1,edge+m+1,zhzs);//排序
for(register int i=1;i<=n;i++)
baba[i]=i;//初始化
for(register int i=1;i<=m;i++)
if(find(edge[i].u)!=find(edge[i].v))
{
ans+=edge[i].w;
he(edge[i].u,edge[i].v);
}
cout<<ans;
return 0;
}
```
------------
# 6.最短路
参考了《信息学奥赛一本通 提高篇》和《全国青少年信息学竞赛培训教材（复赛篇）》
## （1）~~瞎扯淡~~ 定义：
- 从城市A到城市B，可以直达也可以途径其他城市等多种走法到达，问哪一条走法最省时省力？
- 计算最短路径时，分为SSSP（单源最短路径）和APSP（所有点对之间的最短路径）
## （2）迪杰斯特拉算法（Dijkstra）：
- 算法思想：如果图是不带负权的图，我们可以用类似prim算法的贪心思想，从起点s每次新扩展一个距离最短的点，再以这个点为中间点，更新起点到其他所有点的距离。因为边权都是正的，所以不会存在一个距离更短的没被扩展的点，所以这个最短距离永远不会被改变。
- 实现：用两个一维数组b[i],dis[i]分别表示改点是否被扩展，和起点到改点的最短距离。
- 关于算法：复杂度：O(n^2).加堆优化后可以降到O((n+m)logm).有负边权就崩了。
普通版的：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct zhzs
{suanfa
int next,to,w;
}edge[500001];
int n,m,s,ans=0,x,y,z,k=0,b[10001],dis[10001],minn,t,head[10001];
inline void add(int u,int v,int w)
{
edge[++k].to=v;
edge[k].next=head[u];
edge[k].w=w;
head[u]=k;
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(register int i=1;i<=n;i++)
dis[i]=2147483647;
for(register int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
b[s]=1;
for(register int i=head[s];i;i=edge[i].next)
dis[edge[i].to]=min(dis[edge[i].to],edge[i].w);
dis[s]=0;
for(register int i=1;i<=n;i++)
{
minn=2147483647;
t=0;
for(register int j=1;j<=n;j++)
if(b[j]==0&&minn>dis[j])
{
minn=dis[j];
t=j;
}
b[t]=1;
for(register int j=head[t];j;j=edge[j].next)
if(b[edge[j].to]==0)
dis[edge[j].to]=min(dis[edge[j].to],dis[t]+edge[j].w);
}
for(register int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
```
堆优化：
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
struct zhzs
{
int next,to;
long long w;
}edge[500001];
int n,m,s,x,y,z,k=0,b[10001],head[500001];
long long dis[10001];
inline void add(int u,int v,long long w)
{
k++;
edge[k].to=v;
edge[k].next=head[u];
edge[k].w=w;
head[u]=k;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(b,0,sizeof(b));
cin>>n>>m>>s;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
for(register int i=1;i<=n;i++)
dis[i]=2147483647;
dis[s]=0;
q.push(make_pair(0,s));
while(q.size()!=0)
{
int t=q.top().second;
q.pop();
if(b[t]==0)
{
b[t]=1;
for(register int i=head[t];i;i=edge[i].next)
{
dis[edge[i].to]=min(dis[edge[i].to],dis[t]+edge[i].w);
q.push(make_pair(dis[edge[i].to],edge[i].to));
}
}
}
for(register int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
```
## （3）弗洛伊德（Floyd）算法：
- 缺点：要求无负环，解决多源最短路问题。
- 算法思路：弗洛伊德算法是一种O(n^3)的dp思路，设dis[i][j][k]表示路径中间只允许经过结点1..k的情况下，i到j的最短路距离。它有两种情况：1.最短路经过k：dis[i][j][k]=dis[i][k][k-1]+dis[k][j][k-1].2.最短路不经过点k,dis[i][j][k]=dis[i][j][k-1];状态转移方程:dis[i][j][k]=min(dis[i][k][k-1]+dis[k][j][k-1],dis[i][j][k-1]).
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[1001][1001],x,y,z;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
a[x][y]=z;
}
for(register int k=1;k<=n;k++)
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++)
if((i!=j)&&(j!=k)&&(i!=k)&&(a[i][j]>a[i][k]+a[k][j]))
a[i][j]=a[i][k]+a[k][j];
for(register int i=1;i<=n;cout<<endl,i++)
for(register int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
return 0;
}
```
## （4）Bellman-Ford算法：
- 其实就是所谓没加队列优化的SPFA....复杂度相对很不友好，O（VE）。但是代码好打得多。它其实就是每个边都循环一遍来松弛,逼近真实值，一共循环n次。弱化版单元最短路只有70.
```cpp
#include<bits/stdc++.h>
using namespace std;
int u[500010],v[500010],w[500010],h[10010],ne[500010];
long long dis[10010];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n,m,s;
cin>>n>>m>>s;
fill(dis+1,dis+n+1,2147483647);
for(int q=1;q<=m;q++){
cin>>u[q]>>v[q]>>w[q];
ne[q]=h[u[q]],h[u[q]]=q;
}
dis[s]=0;
for(int q=1;q<=n;q++){
for(int w1=1;w1<=m;w1++){
dis[v[w1]]=min(dis[v[w1]],dis[u[w1]]+w[w1]);
}
}
for(int q=1;q<=n;q++)
cout<<dis[q]<<" ";
}
```
- ~~竟然有人觉得需要了解如何用bellman判负环~~ 有必要讲一讲怎么用它判负环。其实在读入的时候取最小权值，最后输出的时候再判断一下有没有比最小权值最小的值就行了。~~本人懒死不想优化判负环啦~~
```cpp
#include<bits/stdc++.h>
using namespace std;
int u[500010],v[500010],w[500010],h[10010],ne[500010];
long long dis[10010];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n,m,s,min1=1e9;
cin>>n>>m>>s;
fill(dis+1,dis+n+1,2147483647);
for(int q=1;q<=m;q++){
cin>>u[q]>>v[q]>>w[q];
ne[q]=h[u[q]],h[u[q]]=q;
min1=min(min1,w[q]);
}
dis[s]=0;
for(int q=1;q<=n;q++){
for(int w1=1;w1<=m;w1++){
dis[v[w1]]=min(dis[v[w1]],dis[u[w1]]+w[w1]);
}
}
int p=1;
for(int q=1;q<=n;q++){
if(dis[q]<min1)p=0;
cout<<dis[q]<<" ";
}
if(p==0)cout<<endl<<"YES";
else cout<<endl<<"NO";
}
```
## （5）SPFA算法：
- 实际上，SPFA算法在国际上通称为“队列优化Bellman-Ford算法”，仅在中国流行“SPFA算法”的称呼。
- [关于SPFA算法它已经死了](https://www.luogu.org/discuss/show/52693)
- 算法思路：设立一个队列来保存待优化的结点，优化时每次取出队首结点ｕ，并且用ｕ点当前的最短路估值的u点所指向的结点v进行松弛操作，如果v点的最短路估值被调整，且v点不在队列里就将v放在队尾。直到队列为空。
- SPFA算法同样可以判负环，如果某个点弹出队列次数超过n-1次，则存在负环。
```cpp
#include<iostream>suanfa
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
queue<int> q;
struct zhzs
{
int next,to;
long long w;
}edge[200001];
int n,m,s,x,y,z,k=0,b[100001],head[200001];
long long dis[100001];
inline void add(int u,int v,long long w)
{
k++;
edge[k].to=v;
edge[k].next=head[u];
edge[k].w=w;
head[u]=k;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(b,0,sizeof(b));
cin>>n>>m>>s;
for(register int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
}
for(register int i=1;i<=n;i++)
dis[i]=2147483647;
dis[s]=0;
q.push(s);
b[s]=1;
while(q.size())
{
int t=q.front();
b[t]=0;
q.pop();
for(register int i=head[t];i;i=edge[i].next)
if(dis[edge[i].to]>dis[t]+edge[i].w)
{
dis[edge[i].to]=dis[t]+edge[i].w;
if(b[edge[i].to]==0)
{
q.push(edge[i].to);
b[edge[i].to]=1;
}
}
}
for(register int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
```