图论-最短路径问题

0、摘要

1、Dijkstra算法

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

1.1 算法基本思想

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

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

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

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

1.2 算法设计

1.2.1 数据结构

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

1.2.2 初始化

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

1.2.3 算法过程

1.2.3.1 找最小

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

1.2.3.2 松弛操作

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

重复执行1.2.3.1和1.2.3.2，直到 $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

1.3.1 算法分析

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

1.4 优化后的Dijkstra板子

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

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

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

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

#include
#include
#include
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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

2、Floyd算法

2.1 算法基本思想

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

2.2 算法设计

2.2.1 数据结构

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

2.2.2 初始化

• $dist[i][j]=G[i][j]$
• 如果节点 $i$ 到节点 $j$ 有边相连，$p[i][j]=i$，否则$p[i][j]=-1$。

例子：

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}}
1
2
3
4
5
6
7
8

2.2.3 插点

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

如果$dist[i][j]>dist[i][k]+dist[k][j]$，则$dist[i][j]=dist[i][k]+dist[k][j]$，并记录节点 $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]<<"-->";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.4 Floyd例子

#include
#include
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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

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)$ ，如果 $dist[e[j].b]>dist[e[j.a]+e[j].w$，则 $dist[e[j].b]=dist[e[j].a]+e[j].w$ 。
• $dist[v]$ 表示从源点到节点v的最短路径长度。

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

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

3.3 板子

#include
#include
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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

• 时间复杂度：算法中对每条边进行松弛操作，重复 $n-1$ 次，时间复杂度为 $O(nm)$ 。
• 空间复杂度：包含数组$e[]$、$dist[]$， 空间复杂度为 $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 数据结构

• 链式前向星存储图，$dist[j]$ 记录从源点到节点的最短路径长度

• $vis[i]$ 标记节点i是否在队列中，

• $sum[i]$ 记录节点 $i$ 入队次数

4.2.2 创建队列

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

4.2.3 松弛操作

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

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

4.3 板子

#include
#include
#include
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
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88