【C++】图的最短路径

• 最短路径
• 求最短路径长度的算法
• • Floyed-Warshall算法
  • • 代码实现
  • Dijkstra算法
  • • 代码实现
  • Bellman-Ford算法
  • • 代码实现
  • SPFA算法
  • • 代码实现
    • 优化做法

我们把边上带有权值的图称作带权图、有权图。一张连通图内任意两点间都会有不同的路径连接，最短路径指的就是路径上所有边的权值和最小的一条路

有四种方法可以解决最短路径问题，但对于边上权值的不同情况，有些方法无法使用

注：边的权值可能为负。如果一个环上的权值之和是负数，则称这个环是负权回路，简称负环

Floyed-Warshall，简称Floyed（弗洛伊德），是相对简单的最短路径算法，可计算所有结点之间的最短路径（APSP），适用于出现负权的情况，但时间复杂度高达O(n³)，所以仅仅能用在顶点数量较少的情况（如果只有100多就放心用）

算法描述：

1. 输入，初始化dist数组，赋上边权，如果不联通则设定为一个很大的值即可（通常为INT_MAX）
2. 通过三层循环更新顶点之间的最短路径长度
3. 结束，dist[i][j]的值就是 i 到 j 的最短路径长度

void floyed(int n)//n为顶点数 
{
	int i,j,k;
	for(k=1;k<=n;k++)//循环中间点k
		for(i=1;i<=n;i++)//循环起点i
			for(j=1;j<=n;j++)//循环终点j
				if(dist[i][k]!=INT_MAX&&dist[k][j]!=INT_MAX&&dist[i][j]>dist[i][k]+dist[k][j])
				{
					//如果点i到点k的距离加上点k到点j的距离，小于原先点i到点j的距离，那么就用这个更短的更新原先的距离
					dist[i][j]=dist[i][k]+dist[k][j];
				}

迪杰斯特拉算法，一种单源最短路径算法（SSSP），只能计算一个点到其他所有点的最短路径，也就是起点只能有一个。它的时间复杂度是O(n²)，不能处理有负权的情况

算法描述（队列做法）：（设起点为s）

1. 初始化dist[s]=0，其余为一个很大的值（通常为INT_MAX）
2. 进入循环，直到优先队列为空
3. 用没被访问过的点中找到一个点u，使得dist[u]最小，并用dist[u]更新与之相连的点的dist，并把这些点全部入队
4. 优先队列为空，算法结束，dist[u]即为s到u的最短路径

typedef struct node
{
	int v,w;
	bool operator < (const struct node & t) const
	{
		return w>t.w;
	}
}NODE,*PNODE;
NODE tmp,tmp1;
priority_queue pq;
//省略全局变量与数组
void dijkstra(int s)
{
	int i;
	tmp.v=s;
	tmp.w=0;
	pq.push(tmp);
	while(!pq.empty())
	{
		tmp=pq.top();
		pq.pop();
		visited[tmp.v]=1;
		dist[tmp.v]=tmp.w;
		for(i=head[tmp.v];i;i=nxt[i])
		{
			tmp1.v=to[i];
			tmp1.w=weight[i]+dist[tmp.v];
			if(visited[tmp1.v])
				continue;
			pq.push(tmp1);
		}
	}
}

贝尔曼福特算法，简称Ford（福特），也是一个单源最短路径算法（SSSP），用来计算一个点到其他所有点的最短路径算法
有意思的是，它能处理负权情况，但无法处理负权回路（负环），后文会解释说明
时间复杂度为O(NE)，N为顶点数，E是边数

思路没什么好说的，看代码吧：

typedef struct edge
{
	int u,v,w;
}EDGE,*PEDGE;
//省略全局变量与数组
void bellmanford(int s)
{
	int i;
	for(i=1;i<=n;i++)
		dist[i]=INT_MAX;
	dist[s]=0;
	//以下两层循环算最短路，但是可能出现负环，出现负环是没有最短路的
	for(i=1;idist[arr[j].u]+arr[j].w)
				dist[arr[j].v]=dist[arr[j].u]+arr[j].w;
}

Bellman-Ford算法会在负权回路上走无数圈，路径值最终达到无穷小，所以会出错
但这个算法好在可以给出让我们判断负环的信息：

方法：算法结束再枚举一次，如果还能更新最短路，说明有负环，如果不能，说明没负环（用一个标志记录）

	flag=0;
	for(j=1;j<=m;j++)
	{
		if(dist[arr[j].u]!=INT_MAX&&dist[arr[j].v]>dist[arr[j].u]+arr[j].w)
		{
			flag=1;
			break; 
		}
	}

SPFA（Shortest Path Faster Algorithm 最短路径快速算法）是Bellman-Ford的队列实现方法，也可以看做一种优化
它是单源最短路径算法（SSSP），可以处理负权与负权回路
时间复杂度最坏为O(NE)，E是边数，N是顶点数，所以在正权图上应当使用效率更高的Dijkstra算法

void spfa(int index)
{
	int i,tmp;
	for(i=1;i<=n;i++)
		dist[i]=INT_MAX;
	dist[index]=0;
	visited[index]=1;
	dq.push_back(index);
	while(!dq.empty())
	{
		tmp=dq.front();
		dq.pop_front();
		visited[tmp]=0;
		cnt[tmp]++;//用来算负权回路 ，题目明确没有时可以不写
		if(cnt[tmp]>n-1)//用来算负权回路 ，题目明确没有时可以不写
			break;
		for(i=head[tmp];i;i=next[i])
		{
			if(dist[tmp]!=INT_MAX&&weight[i]+dist[tmp]
				dist[to[i]]=weight[i]+dist[tmp];
				if(!visited[to[i]])
				{
					if(!dq.empty()&&dist[to[i]] 
优化做法 
但在只记得SPFA而忘记了Floyed算法，而又正好遇到了适合Floyed做法，SPFA会爆时间的题目时，就要往上加一点点的优化了
 
 
 
注：此处涉及面向对象做法
 
 
typedef struct node
{
	int u;
	static int dist[100001];//静态成员变量，被所有这个类型的变量共享 ，这里都涉及到了c++面向对象的知识点  
	bool operator < (const struct node & t) const
	{
		return dist[u]0};//需要在外部初始化 ，这里都涉及到了c++面向对象的知识点 
int head[],visited[],cnt[],pre[];//顶点数
int nxt[],to[],weight[];//边数，如果是无向图边数*2
int tot;
priority_queue pq;
void add_edge(int u,int v,int w)
{
	nxt[++tot]=head[u];
	to[tot]=v;
	weight[tot]=w;
	head[u]=tot;
} 
void spfa(int index)//带优化 
{
	int i;
	NODE tmp,tmp1; 
	for(i=1;i<=n;i++)
		dist[i]=INT_MAX;
	dist[index]=0;
	visited[index]=1;
	tmp.u=index; 
	pq.push(tmp);
	while(!pq.empty())
	{
		tmp=pq.top();
		pq.pop();
		visited[tmp.u]=0;
		cnt[tmp.u]++;
		if(cnt[tmp.u]>n-1)
			break;
		for(j=head[tmp.u];j;j=nxt[j])
		{
			v=to[j];
			if(NODE::dist[v]>NODE::dist[tmp.u]+weight[j])//注意这里类静态成员用法 
			{
				NODE::dist[v]=NODE::dist[tmp.u]+weight[j];//注意这里类静态成员用法 
				pre[v]=tmp.u;
				if(!visited[v])  //这样在队列已有的情况下，dist[v]可以被更新成最短路 
				{
					tmp1.u=v;
					pq.push(tmp1);
					visited[v]=1;	
					
				}
			}	
		}		
	}
}