图论-最短路径问题

今天药忘吃喽~ 2024-04-08 08:40 67阅读 0赞

## 图论-最短路径问题 ##

### 0、摘要 ###

<table> 
 <thead> 
 <tr> 
 <th>算法名称</th> 
 <th>用途</th> 
 <th>时间复杂度</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td><code>Dijkstra</code>算法</td> 
 <td>单源最短路问题</td> 
 <td> O ( n 2 ) O(n^2) O(n2) 优化后 O ( n m ) O(nm) O(nm)</td> 
 </tr> 
 <tr> 
 <td><code>Floyd</code>算法</td> 
 <td>各个顶点之间最短路径</td> 
 <td> O ( n 3 ) O(n^3) O(n3)</td> 
 </tr> 
 <tr> 
 <td><code>SPFA</code>算法</td> 
 <td>队列优化</td> 
 <td> O ( k e ) O(ke) O(ke) k k k 为常数， e e e 为边数</td> 
 </tr> 
 <tr> 
 <td><code>Bellman-Ford</code>算法</td> 
 <td>负权值 判负环 单源最短路问题</td> 
 <td> O ( n e ) O(ne) O(ne) n n n 为节点数， e e e 为边数</td> 
 </tr> 
 </tbody> 
</table>

### 1、`Dijkstra`算法 ###

如何求源点到其他各节点的最短路径呢？提到单源最短路径，必然绕不开一个著名人物——迪杰斯特拉。迪杰斯特拉，荷兰计算机科学家，早年钻研物理及数学，后转而研究计算学，1972年 曾因`Dijkstra`算法获得素有“计算机科学界诺贝尔奖”之称的图灵奖。

#### 1.1 算法基本思想 ####

Dijkstra算法是解决单源最短路径问题的**贪心算法**，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出源点到其他各个节点的最短路径。

`Dijkstra`算法基本思想：将节点集合划分为两部分——集合  S S S 和  V − S V-S V−S 。其中，

*   S S S 中的节点的最短路径已经确定
 *   V − S V-S V−S 中的节点的最短路径待定。
 *  从源点出发只经过  S S S 中的节点到达  V − S V-S V−S 中的节点的路径称为特殊路径。

`Dijkstra`算法的贪心策略是选择最短的特殊路径长度  d i s t \[ \] dist\[\] dist\[\] ，并将节点  t t t 加入到集合  S S S 中，同时借助  t t t 更新数组  d i s t \[ \] dist\[\] dist\[\] 。一旦  S S S 包含了所有节点， d i s t \[ \] dist\[\] dist\[\] 就是从源点到其他节点的最短路径长度。

![在这里插入图片描述][f1ae64eaad0c4dfa8b2fa2d1c5397814.png]

#### 1.2 算法设计 ####

##### 1.2.1 数据结构 #####

*  邻接矩阵  G \[ \] \[ \] G\[\]\[\] G\[\]\[\] 存储图
 *   d i s t \[ i \] dist\[i\] dist\[i\] 记录从源点到节点的最短路径长度
 *   p \[ i \] p\[i\] p\[i\] 记录最短路径上节点的直接前驱
 *  如果  f l a g \[ i \] flag\[i\] flag\[i\] 等于true，说明节点记加入集合  S S S ，否则  i i i 属于集合  V − S V-S V−S 。

##### 1.2.2 初始化 #####

假设  u u u 为源点，令集合  S = u S=\{u\} S=u ，对  V − S V-S V−S 集合中的节点  i i i ，初始化  d i s t \[ i \] = G \[ u \] \[ i \] dist\[i\]=G\[u\]\[i\] dist\[i\]=G\[u\]\[i\] ， 如果源点u到节点有边相连，初始化  p \[ i \] = u p\[i\]=u p\[i\]=u ，否则  p \[ i \] = − 1 p\[i\]=-1 p\[i\]=−1 。

##### 1.2.3 算法过程 #####

###### 1.2.3.1 找最小 ######

按照贪心策略来查找  V − S V-S V−S 集合中  d i s t \[ \] dist\[\] dist\[\] 最小的节点  t t t ， t t t 就是  V − S V-S V−S 集合中距离源点  u u u 最近的节点。将节点加入集合  S S S 中。

###### 1.2.3.2 松弛操作 ######

对  V − S V-S V−S 集合中所有节点  j j j ，考察是否可以借助  t t t 得到更短的路径。如果源点  u u u 经过到  j j j 的路径更短， d i s t \[ j \] > d i s t \[ t \] + G \[ \] \[ \] dist\[j\]>dist\[t\]+G\[\]\[\] dist\[j\]>dist\[t\]\+G\[\]\[\]，则更新  d i s t \[ j \] = d i s t \[ 1 \] + G \[ t \] \[ j \] dist\[j\]=dist\[1\]+G\[t\]\[j\] dist\[j\]=dist\[1\]\+G\[t\]\[j\] ，即松弛操作，并记录  j j j 的直接前驱为  t t t ，即  p \[ j \] = t p\[j\]=t p\[j\]=t 。

重复执行1.2.3.1和1.2.3.2，直到  V − S V-S V−S 为空。

#### 1.3 邻接矩阵的`Dijkstra`板子 ####

const int N=1005;
 const int INF=0x3f3f3f3f; //无穷大
 int G[N][N], dist[N]; //G[][]为邻接矩阵，dist[i]表示源点到结点的最短路径长度
 int p[N]; //p[i]表示源点到结点的最短路径上i的前驱
 int n,m; //n为结点数，m为边数
 bool flag[N]; //如果flag[i]等于true，说明结点已经加入到集合;否则属于V-S集合
 
 
 void Dijkstra(int u) {
 //u是源点，源点到其它各个顶点的最短路径
 	for(int i=0; i<=n; i++) {
 
 		dist[i]=G[u][i]; //初始化源点u到其他各个顶点的最短路径长度
 		flag[i]=false;
 		if(dist[i]==INF)
 			p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
 		else
 			p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
 	}
 	dist[u]=0;
 	flag[u]=true; //初始时，集合S中只有一个元素：源点u
 	for(int i=0; i<=n; i++) {
 //重复n-1次
 		int temp=INF,t=u;
 		for(int j=0; j<=n; j++) {
 //在集合V-S中寻找距离源点u最近的顶点t
 			if(!flag[j]&&dist[j]<temp) {
 
 				t=j;
 				temp=dist[j];
 			}
 		}
 		if(t==u) return; //找不到t，跳出循环
 		flag[t]=true; //否则，将t加入集合
 		for(int j=1; j<=n; j++) {
 //判断V-S集合中的节点是否可以借助t更新dist[],松弛操作
 			if(!flag[j]&&dist[j]>dist[t]+G[t][j]) {
 
 				dist[j]=dist[t]+G[t][j]; // 更新最短距离
 				p[j]=t; //记录前驱
 			}
 		}
 	}
 }
 
 void findp(int u){
 
 	if(u==-1){
 
 return;
 }
 	findp(p[u]);
 	cout<<u<<"\t";
 }

##### 1.3.1 算法分析 #####

*  时间复杂度：找最小值和松弛操作本身各执行 n n n次，需要重复 n − 1 n-1 n−1次， 总执行次数均为 n 2 n^2 n2，时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
 *  空间复杂度：包含数组 f 1 a g \[ \] f1ag\[\] f1ag\[\]、  p \[ \] p\[\] p\[\]， 空间复杂度为 O ( n ) O(n) O(n)。

#### 1.4 优化后的`Dijkstra`板子 ####

##### 1.4.1 算法优化1——找最小值 #####

按照贪心策略查找  V − S V-S V−S 集合中  d i s t \[ \] dist\[\] dist\[\] 最小的节点  t t t ，其时间复杂度为  O ( n ) O(n) O(n) ，如果使用优先队列，则每次找最小值时间复杂度降为  O ( l o g n ) O(logn) O(logn) ，找最小值的总时间复杂度为  O ( n l o g n ) O(nlogn) O(nlogn) 。

##### 1.4.2 算法优化2——松弛操作 #####

如果采用邻接表或链式前向星存储，松弛操作就不用每次执行  n n n 次，而是执行节点  t t t 的邻接点数（  t t t 的出度），所有节点的出度之和等于边数  m m m ，松弛操作的总时间复杂度为  O ( m ) O(m) O(m)

#include<iostream>
 #include<cstring>
 #include<stack>
 using namespace std;
 const int MaxVnum=100; //城市的个数可修改
 const int INF=0x3f3f3f3f; //无穷大
 int dist[MaxVnum],p[MaxVnum];//最短距离和前驱数组
 bool flag[MaxVnum]; //如果s[i]等于true，说明顶点i已经加入到集合S;否则顶点i属于集合V-S
 typedef string VexType; //顶点的数据类型，根据需要定义
 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1
 typedef struct{
 
 	VexType Vex[MaxVnum];
 	EdgeType Edge[MaxVnum][MaxVnum];
 	int vexnum,edgenum; //顶点数，边数
 }AMGraph;
 
 int locatevex(AMGraph G,VexType x){
 
 for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
 		if(x==G.Vex[i])
 	return i;
 return -1;//没找到
 }
 
 void CreateAMGraph(AMGraph &G){
 
 int i,j,w;
 VexType u,v;
 cout<<"请输入顶点数："<<endl;
 cin>>G.vexnum;
 cout<<"请输入边数:"<<endl;
 cin>>G.edgenum;
 cout<<"请输入顶点信息:"<<endl;
 for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
 cin>>G.Vex[i];
 for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵为无穷大
 		for(int j=0;j<G.vexnum;j++)
 			G.Edge[i][j]=INF;
 cout<<"请输入每条边依附的两个顶点及权值："<<endl;
 while(G.edgenum--){
 
 		cin>>u>>v>>w;
 		i=locatevex(G,u);//查找顶点u的存储下标
 		j=locatevex(G,v);//查找顶点v的存储下标
 		if(i!=-1&&j!=-1)
 			G.Edge[i][j]=w; //有向图邻接矩阵
 		else{
 
 			cout<<"输入顶点信息错！请重新输入！"<<endl;
 			G.edgenum++;//本次输入不算
 		}
 }
 }
 
 void Dijkstra(AMGraph G,int u){
 
 	for(int i=0;i<G.vexnum;i++){
 
 		dist[i]=G.Edge[u][i]; //初始化源点u到其他各个顶点的最短路径长度
 		flag[i]=false;
 		if(dist[i]==INF)
 			p[i]=-1; //源点u到该顶点的路径长度为无穷大，说明顶点i与源点u不相邻
 		else
 			p[i]=u; //说明顶点i与源点u相邻，设置顶点i的前驱p[i]=u
 	}
 dist[u]=0;
 flag[u]=true; //初始时，集合S中只有一个元素：源点u
 for(int i=0;i<G.vexnum;i++){
 
 int temp=INF,t=u;
 for(int j=0;j<G.vexnum;j++) //在集合V-S中寻找距离源点u最近的顶点t
 			if(!flag[j]&&dist[j]<temp){
 
 	t=j;
 	temp=dist[j];
 	}
 if(t==u) return; //找不到t，跳出循环
 flag[t]=true; //否则，将t加入集合
 for(int j=0;j<G.vexnum;j++)//更新V-S中与t相邻接的顶点到源点u的距离
 			if(!flag[j]&&G.Edge[t][j]<INF)
 				if(dist[j]>(dist[t]+G.Edge[t][j])){
 
 					dist[j]=dist[t]+G.Edge[t][j];
 					p[j]=t;
 	}
 }
 }
 
 void findpath(AMGraph G,VexType u){
 
 	int x;
 	stack<int>S;
 	cout<<"源点为："<<u<<endl;
 	for(int i=0;i<G.vexnum;i++){
 
 		x=p[i];
 		if(x==-1&&u!=G.Vex[i]){
 
 		 cout<<"源点到其它各顶点最短路径为："<<u<<"--"<<G.Vex[i]<<" sorry,无路可达"<<endl;
 		 continue;
 		}
 		while(x!=-1){
 
 			S.push(x);
 			x=p[x];
 		}
 		cout<<"源点到其它各顶点最短路径为：";
 		while(!S.empty()){
 
 			cout<<G.Vex[S.top()]<<"--";
 			S.pop();
 		}
 		cout<<G.Vex[i]<<" 最短距离为："<<dist[i]<<endl;
 	}
 }
 
 int main(){
 
 AMGraph G;
 int st;
 VexType u;
 CreateAMGraph(G);
 cout<<"请输入源点的信息:"<<endl;
 cin>>u;
 st=locatevex(G,u);//查找源点u的存储下标
 Dijkstra(G,st);
 cout<<"小明所在的位置:"<<u<<endl;
 for(int i=0;i<G.vexnum;i++){
 
 cout<<"小明:"<<u<<" - "<<"要去的位置:"<<G.Vex[i];
 if(dist[i]==INF)
 			cout<<" sorry,无路可达"<<endl;
 else
 			cout<<" 最短距离为:"<<dist[i]<<endl;
 }
 findpath(G,u);
 return 0;
 }
 /*
 5 8
 1 2 3 4 5
 1 2 2
 1 3 5
 2 3 2
 2 4 6
 3 4 7
 3 5 1
 4 3 2
 4 5 4
 1
 */

### 2、`Floyd`算法 ###

#### 2.1 算法基本思想 ####

`Dijkstra`算法用于求从源点到其他各个节点的最短路径。如果求解任意两个节点之间的最短路径，则需要以每个节点为源点，重复调用  n n n 次 `Dijkstra`算法。其实完全没必要这么麻烦，`Floyd`算法可用于求解任意两个节点间的最短路径。`Floyd`算法又被称为插点法，其算法核心是在节点  i i i 与节点  j j j 之间插入节点  k k k ，看看是否可以缩短节点  i i i 与节点  j j j 之间的距离（松弛操作）

#### 2.2 算法设计 ####

##### 2.2.1 数据结构 #####

*  邻接矩阵  G \[ \] \[ \] G\[\]\[\] G\[\]\[\] 存储图
 *   d i s t \[ i \] \[ j \] dist\[i\]\[j\] dist\[i\]\[j\] 记录从节点  i i i 到节点  j j j 的最短路径长度
 *   p \[ i \] \[ j \] p\[i\]\[j\] p\[i\]\[j\] 记录 节点  i i i 到节点  j j j 的最短路径上节点  j j j 的直接前驱。

##### 2.2.2 初始化 #####

*   d i s t \[ i \] \[ j \] = G \[ i \] \[ j \] dist\[i\]\[j\]=G\[i\]\[j\] dist\[i\]\[j\]=G\[i\]\[j\]
 *  如果节点  i i i 到节点  j j j 有边相连， p \[ i \] \[ j \] = i p\[i\]\[j\]=i p\[i\]\[j\]=i，否则 p \[ i \] \[ j \] = − 1 p\[i\]\[j\]=-1 p\[i\]\[j\]=−1。

例子：

![在这里插入图片描述][4c982ce0f3234fecad996b722fca5bd6.png]

dist[][]={
        {
        0,1,-1,4},
    		 {
        -1,0,9,2},
    		 {
        3,5,0,8},
    		 {
        -1,-1,6,0}}
    p[][]={
        {
        -1,0,-1,0},
    	   {
        -1,-1,1,1},
    	   {
        2,2,-1,2},
    	   {
        -1,-1,3,-1}}

##### 2.2.3 插点 #####

其实就是在节点  i i i、 j j j 之间插入节点  k k k ，看是否可以缩短节点  i i i、 j j j 之间的距离（松弛操作）。

如果 d i s t \[ i \] \[ j \] > d i s t \[ i \] \[ k \] + d i s t \[ k \] \[ j \] dist\[i\]\[j\]>dist\[i\]\[k\]+dist\[k\]\[j\] dist\[i\]\[j\]>dist\[i\]\[k\]\+dist\[k\]\[j\]，则 d i s t \[ i \] \[ j \] = d i s t \[ i \] \[ k \] + d i s t \[ k \] \[ j \] dist\[i\]\[j\]=dist\[i\]\[k\]+dist\[k\]\[j\] dist\[i\]\[j\]=dist\[i\]\[k\]\+dist\[k\]\[j\]，并记录节点  j j j 的前驱，  p \[ j \] \[ i \] = p \[ k \] \[ j \] p\[j\]\[i\]=p\[k\]\[j\] p\[j\]\[i\]=p\[k\]\[j\] 。

#### 2.3 邻接矩阵的 `Floyd`板子 ####

void Floyd() {
 //用FLoyd算法求有向网G中各对顶点和j之间的最短路径
 	for(int i=0; i<n; i++) {
 // 初始化
 		for(int j=0; j<n; j++) {
 
 			if(i==j) {
 
 				dist[i][j]=0;//自已到自己最短距离为0
 			} else {
 
 				dist[i][j]=G[i][j];
 			}
 			if(dist[i][j]<INF&&i!=j) {
 
 				p[i][j]=i; // 如果i和j之间有边，则将j的前驱置为i
 			} else {
 
 				p[i][j]=-1; //如果i和j之间无边，则将j的前驱置为-1
 			}
 
 		}
 		for(int k=0; k<n; k++) {
 
 			for(int i=0; i<n; i++) {
 
 				for(int j=0; j<n; j++) {
 
 					if(dist[i][k]+dist[k][j]<dist[i][j]) {
 //从i经k到j的- -条路径更短
 						dist[i][j]=dist[i][k]+dist[k][j]; //更新dist[i][j]
 						p[i][j]=p[k][j]; //更改的前驱
 					}
 				}
 			}
 		}
 	}
 }
 
 void DisplayPath(int s,int t) {
 //输出s到t的最短路径
 	if(p[s][t]!=-1) {
 
 		DisplayPath(s,p[s][t]);
 		cout<<p[s][t]<<"-->";
 	}
 }

#### 2.4 `Floyd`例子 ####

#include<iostream>
 #include<cstring>
 using namespace std;
 const int MaxVnum=100; //顶点数最大值
 const int INF=0x3f3f3f3f; // 无穷大
 typedef string VexType; //顶点的数据类型，根据需要定义
 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1
 typedef struct{
 
 	VexType Vex[MaxVnum];
 	EdgeType Edge[MaxVnum][MaxVnum];
 	int vexnum,edgenum; //顶点数，边数
 }AMGraph;
 int dist[MaxVnum][MaxVnum],p[MaxVnum][MaxVnum];
 
 int locatevex(AMGraph G,VexType x){
 
 for(int i=0;i<G.vexnum;i++)//查找顶点信息的下标
 		if(x==G.Vex[i])
 			return i;
 return -1;//没找到
 }
 
 void CreateAMGraph(AMGraph &G){
 //创建无向图的邻接矩阵
 int i,j,w;
 VexType u,v;
 cout<<"请输入顶点数："<<endl;
 cin>>G.vexnum;
 cout<<"请输入边数:"<<endl;
 cin>>G.edgenum;
 cout<<"请输入顶点信息:"<<endl;
 for(int i=0;i<G.vexnum;i++)//输入顶点信息，存入顶点信息数组
 cin>>G.Vex[i];
 for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵所有值为0，若是网，则初始化为无穷大
 		for(int j=0;j<G.vexnum;j++)
 			if(i!=j)
 	G.Edge[i][j]=INF;
 	else
 	G.Edge[i][j]=0; //注意i==j时，设置为0
 cout<<"请输入每条边依附的两个顶点及权值："<<endl;
 while(G.edgenum--){
 
 		cin>>u>>v>>w;
 		i=locatevex(G,u);//查找顶点u的存储下标
 		j=locatevex(G,v);//查找顶点v的存储下标
 		if(i!=-1&&j!=-1)
 			G.Edge[i][j]=w; //有向图邻接矩阵存储权值
 }
 }
 
 void Floyd(AMGraph G){
 //用Floyd算法求有向网G中各对顶点i和j之间的最短路径
 	int i,j,k;
 for(i=0;i<G.vexnum;i++) 		//各对结点之间初始已知路径及距离
 		for(j=0;j<G.vexnum;j++){
 
 			dist[i][j]=G.Edge[i][j];
 			if(dist[i][j]<INF&&i!=j)
 				p[i][j]=i; 	//如果i和j之间有弧，则将j的前驱置为i
 			else p[i][j]=-1; //如果i和j之间无弧，则将j的前驱置为-1
 		}
 	for(k=0;k<G.vexnum;k++)
 		for(i=0;i<G.vexnum;i++)
 			for(j=0;j<G.vexnum;j++)
 				if(dist[i][k]+dist[k][j]<dist[i][j]){
 //从i经k到j的一条路径更短
 					dist[i][j]=dist[i][k]+dist[k][j]; //更新dist[i][j]
 					p[i][j]=p[k][j]; //更改j的前驱
 				}
 }
 
 void print(AMGraph G){
 
 int i,j;
 for(i=0;i<G.vexnum;i++){
 //输出最短距离数组
 for(j=0;j<G.vexnum;j++)
 cout<<dist[i][j]<<"\t";
 cout<<endl;
 }
 cout<<endl;
 for(i=0;i<G.vexnum;i++){
 //输出前驱数组
 for(j=0;j<G.vexnum;j++)
 cout<<p[i][j]<<"\t";
 cout<<endl;
 }
 }
 
 void DisplayPath(AMGraph G,int s,int t){
 //显示最短路径
 	if(p[s][t]!=-1){
 
 		DisplayPath(G,s,p[s][t]);
 		cout<<G.Vex[p[s][t]]<<"-->";
 	}
 }
 
 int main(){
 
 VexType start,destination;
 int u,v;
 AMGraph G;
 CreateAMGraph(G);
 Floyd(G);
 print(G);
 	cout<<"请依次输入路径的起点与终点的名称：";
 	cin>>start>>destination;
 	u=locatevex(G,start);
 	v=locatevex(G,destination);
 	DisplayPath(G,u,v);
 	cout<<G.Vex[v]<<endl;
 	cout<<"最短路径的长度为："<<dist[u][v]<<endl;
 	cout<<endl;
 return 0;
 }
 /*
 4 8
 0 1 2 3
 0 1 1
 0 3 4
 1 2 9
 1 3 2
 2 0 3
 2 1 5
 2 3 8
 3 2 6
 0 2
 */

### 3、`Bellman-Ford`算法 ###

#### 3.1 算法基本思想 ####

`Bellman-Ford`算法用于求解单源最短路径问题，由理查德●贝尔曼和莱斯特●福特提出。该算法的优点是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但是，对该算法可以进行若干种优化，以提高效率。

`Bellman-Ford`算法与 `Dijkstra`算法类似，都以松弛操作为基础。`Dijkstra`算法以贪心法选取未被处理的具有最小权值的节点，然后对其邻接点进行松弛操作。`Bellman-Ford`算法对所有边进行松弛操作，共 `n-1`次，因为负环可以无限制地减少最短路径长度，所以如果第 `n`次操作仍可松弛，则一定存在负环。

#### 3.2 算法设计 ####

##### 3.2.1 数据结构 #####

因为需要利用边进行松弛，因此采用边集。

数组存储。每条边都有三个域：两个端点`a`、`b`和边权 `w`。

##### 3.2.2 松弛操作 #####

*  对所有的边  j ( a , b , w ) j(a,b,w) j(a,b,w) ，如果  d i s t \[ e \[ j \] . b \] > d i s t \[ e \[ j . a \] + e \[ j \] . w dist\[e\[j\].b\]>dist\[e\[j.a\]+e\[j\].w dist\[e\[j\].b\]>dist\[e\[j.a\]\+e\[j\].w，则  d i s t \[ e \[ j \] . b \] = d i s t \[ e \[ j \] . a \] + e \[ j \] . w dist\[e\[j\].b\]=dist\[e\[j\].a\]+e\[j\].w dist\[e\[j\].b\]=dist\[e\[j\].a\]\+e\[j\].w 。
 *   d i s t \[ v \] dist\[v\] dist\[v\] 表示从源点到节点v的最短路径长度。

重复松弛操作  n − 1 n-1 n−1 次。

再执行一次，如果仍然可以松弛，则说明有负环。

#### 3.3 板子 ####

#include<iostream>
 #include<cstring>
 using namespace std;
 struct node{
 
 	int a,b,w;
 }e[210];
 int dis[110];
 int n,m,cnt=0;
 
 void add(int a,int b,int w){
 
 	e[cnt].a=a;
 	e[cnt].b=b;
 	e[cnt++].w=w;
 }
 
 bool bellman_ford(int u){
 //求源点u到其它顶点的最短路径长度，判负环 
 	memset(dis,0x3f,sizeof(dis));
 	dis[u]=0;
 	for(int i=1;i<n;i++){
 //执行n-1次
 		bool flag=false;
 		for(int j=0;j<m;j++)//边数m或cnt
 			if(dis[e[j].b]>dis[e[j].a]+e[j].w){
 
 				dis[e[j].b]=dis[e[j].a]+e[j].w;
 				flag=true;
 			}
 		if(!flag)
 			return false;
 	}
 	for(int j=0;j<m;j++)//再执行1次，还能松弛说明有环
 		if(dis[e[j].b]>dis[e[j].a]+e[j].w)
 			return true;
 	return false;
 }
 
 void print(){
 //输出源点到其它节点的最短距离 
 	cout<<"最短距离："<<endl; 
 	for(int i=1;i<=n;i++)
 		cout<<dis[i]<<" ";
 	cout<<endl;
 }
 
 int main(){
 
 	int a,b,w;
 	cin>>n>>m;
 	for(int i=0;i<m;i++){
 
 		cin>>a>>b>>w;
 		add(a,b,w);
 	}
 	if(bellman_ford(1))//判断负环
 		cout<<"有负环！"<<endl;
 	else
 		print();	
 	return 0;
 }
 /*测试数据1 
 5 8
 1 2 2
 1 3 5
 2 3 2
 2 4 6
 3 4 7
 3 5 1
 4 3 2
 4 5 4
 */
 /*测试数据2，有负环 
 4 4
 1 2 3
 2 3 -4
 3 4 2
 4 2 1
 */

*  时间复杂度：算法中对每条边进行松弛操作，重复  n − 1 n-1 n−1 次，时间复杂度为  O ( n m ) O(nm) O(nm) 。
 *  空间复杂度：包含数组 e \[ \] e\[\] e\[\]、 d i s t \[ \] dist\[\] dist\[\]， 空间复杂度为  O ( n + m ) O(n+m) O(n\+m)。

### 4、`SPFA`算法 ###

#### 4.1 算法基本思想 ####

`SPFA`( `Shortest Path Faster Algorithm`）算法是 `Bellman-Ford`算法的队列优化算法，通常用于求解含负权边的单源最短路径，  
以及判负环。在最坏情况下，`SPFA`算法的时间复杂度和 `Bellman-Ford`算法相同，为`O(nm)`；但在稀疏图上运行效率较高，为`O(km)`，其中k是一个较小的常数。

#### 4.2 算法设计 ####

##### 4.2.1 数据结构 #####

*  链式前向星存储图， d i s t \[ j \] dist\[j\] dist\[j\] 记录从源点到节点的最短路径长度
 *   v i s \[ i \] vis\[i\] vis\[i\] 标记节点i是否在队列中，
 *   s u m \[ i \] sum\[i\] sum\[i\] 记录节点  i i i 入队次数

##### 4.2.2 创建队列 #####

创建一个队列，源点  u u u 入队，标记  u u u 在队列中， u u u 的入队次数加1。

##### 4.2.3 松弛操作 #####

取出队头  x x x，标记  x x x 不在队列中。考察  x x x 的所有出边  i ( x , v , w ) i(x,v,w) i(x,v,w)，如果  d i s t \[ v \] > d i s t \[ x \] + e \[ i \] . w dist\[v\]>dist\[x\]+e\[i\].w dist\[v\]>dist\[x\]\+e\[i\].w，则  d i s t \[ v \] = d i s t \[ x \] + e \[ i \] . w dist\[v\]=dist\[x\]+e\[i\].w dist\[v\]=dist\[x\]\+e\[i\].w。如果节点v不在队列中，如果  v v v 的入队次数加  1 1 1 后大于或等于  n n n，则说明有负环，退出；否则  v v v 入队，标记  v v v 在队列中。

重复松弛操作，直到队列为空。

#### 4.3 板子 ####

#include<iostream>
 #include<cstring>
 #include<queue>
 using namespace std;
 const int maxn=505,maxe=100001;
 int n,m,cnt;
 int head[maxn],dis[maxn],sum[maxn];
 bool vis[maxn];//标记是否在队列中 
 struct node{
 
 	int to,next,w;
 }e[maxe];
 
 void add(int u,int v,int w){
 
 	e[cnt].to=v;
 	e[cnt].next=head[u];
 	e[cnt].w=w;	
 	head[u]=cnt++;
 }
 
 bool spfa(int u){
 
 	queue<int>q;
 	memset(vis,0,sizeof(vis));//标记是否在队列中
 	memset(sum,0,sizeof(sum));//统计入队的次数
 	memset(dis,0x3f,sizeof(dis));
 	vis[u]=1;
 	dis[u]=0;
 	sum[u]++;
 	q.push(u);
 	while(!q.empty()){
 
 		int x=q.front();
 		q.pop();
 		vis[x]=0;
 		for(int i=head[x];~i;i=e[i].next){
 
 			int v=e[i].to;
 			if(dis[v]>dis[x]+e[i].w){
 
 				dis[v]=dis[x]+e[i].w;
 				if(!vis[v]){
 
 					if(++sum[v]>=n)
 						return true;
 					vis[v]=1;
 					q.push(v);
 				}
 			}
 		}
 	}
 	return false;
 }
 
 void print(){
 //输出源点到其它节点的最短距离 
 	cout<<"最短距离："<<endl; 
 	for(int i=1;i<=n;i++)
 		cout<<dis[i]<<" ";
 	cout<<endl;
 }
 
 int main(){
 
 	cnt=0;
 	cin>>n>>m;
 	memset(head,-1,sizeof(head));
 	int u,v,w;
 	for(int i=1;i<=m;i++){
 
 		cin>>u>>v>>w;
 		add(u,v,w);
 	}
 	if(spfa(1))
 		cout<<"有负环！"<<endl;
 	else
 		print();
 	return 0;
 }
 /*测试数据1 
 5 8
 1 2 2
 1 3 5
 2 3 2
 2 4 6
 3 4 7
 3 5 1
 4 3 2
 4 5 4
 */
 /*测试数据2，有负环 
 4 4
 1 2 3
 2 3 -4
 3 4 2
 4 2 1
 */

[f1ae64eaad0c4dfa8b2fa2d1c5397814.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/60291eb268804e34a7b7b3c216e8e2c9.png
[4c982ce0f3234fecad996b722fca5bd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fb7db83f065c405080403182ab852aed.png