单源最短路径

淡淡的烟草味﹌ 2021-12-05 17:07 286阅读 0赞

### 单源最短路径 ###

*  普通版
 *   *  测试输入
     *  测试输出
 *  使用优先队列
 *  SPFA
 *   *  测试输入
     *  测试输出
     *  参考博客
 *  Floyd
 *  Bellman-Ford

# 普通版 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    const int INF = 1<<30;//表示无穷大，两个顶点不存在边
    
    int g[maxn][maxn];//利用邻接矩阵表示有权图
    int n;//表示顶点个数,从1开始编号
    int dist[maxn];//源到其他的距离
    
    void init(){ 
    	for(int i=1;i<=n;i++){ 
    		for(int j=1;j<=n;j++)g[i][j]=INF;
    	}
    }//对图进行初始化
    
    void ShortestDist(int v=1){ 
    	bool reach[maxn]={ 0};
    	reach[v]=true;
    	for(int i=1;i<=n;i++)dist[i]=g[v][i];//对源到个点的距离初始化
        dist[v]=0;//自身到自身为0
    	for(int i=0;i<n;i++){ //循环次数不会超过n
    		int min = INF,index=-1;
    		for(int j=1;j<=n;j++){ 
    			if(!reach[j]&&min>dist[j])min=dist[j],index=j;//未访问顶点的距离最小值
    		}
    		if(index==-1)return ;//已遍历完退出
    		reach[index]=true;//标记该点被访问
    		for(int i=1;i<=n;i++){ 
    			if(g[index][i]+dist[index]<dist[i])dist[i]=g[index][i]+dist[index];//判断是否通过该点取得较小值
    		}
    	}
    }
    
    int main(){ 
    	int m;
    	int a,b,c;
    	scanf("%d%d",&n,&m);
    	init();
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d%d",&a,&b,&c);
    		g[a][b]=g[b][a]=c;
    	}
    	ShortestDist(1);
    	for(int i=1;i<=n;i++){ 
    		printf("%d ",dist[i]);
    	}
    }

## 测试输入 ##

4 4
    1 2 2
    1 3 10 
    2 3 5
    2 4 1

## 测试输出 ##

0 2 7 3

# 使用优先队列 #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    const int INF = 1<<30;//表示无穷大，两个顶点不存在边
    typedef pair<int,int> pa;
    int g[maxn][maxn];//利用邻接矩阵表示有权图
    int n;//表示顶点个数,从1开始编号
    int dist[maxn];//源到其他的距离
    
    void init(){ 
    	for(int i=1;i<=n;i++){ 
    		for(int j=1;j<=n;j++)g[i][j]=INF;
    	}
    }//对图进行初始化
    
    
    void ShortestDist(int v=1){ 
    	priority_queue<pa,vector<pa>,greater<pa> > p;//优先队列，对数对的first进行从小到大
    	bool reach[maxn]={ false};
    	for(int i=1;i<=n;i++){ 
    		dist[i]=g[v][i];
    		p.push(pa(dist[i],i));
    	}
    	int rv=1;//代表已加入最短距离集合
    	reach[v]=true;
    	dist[v]=0;
    	while(!p.empty()){ 
    		if(rv==n)return;//已访问所有顶点，提前退出
    		v = p.top().second;
    		p.pop();
    		if(reach[v])continue;
    		reach[v]=true;
    		rv++;
    		for(int i=1;i<=n;i++){ 
    			if(!reach[i]&&dist[v]+g[v][i]<dist[i])dist[i]=dist[v]+g[v][i],p.push(pa(dist[i],i));//更新
    		}
    	}
    }
    
    int main(){ 
    	int m;
    	int a,b,c;
    	scanf("%d%d",&n,&m);
    	init();
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d%d",&a,&b,&c);
    		g[a][b]=g[b][a]=c;
    	}
    	ShortestDist(1);
    	for(int i=1;i<=n;i++){ 
    		printf("%d ",dist[i]);
    	}
    }

# SPFA #

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e2;
    const int INF = 1<<30;//表示无穷大，两个顶点不存在边
    
    int g[maxn][maxn];//利用邻接矩阵表示有权图
    int n;//表示顶点个数,从1开始编号
    int dist[maxn];//源到其他的距离
    
    void init(){ 
    	for(int i=1;i<=n;i++){ 
    		for(int j=1;j<=n;j++)g[i][j]=INF;
    	}
    }//对图进行初始化
    
    
    /* 可以求解带负边的单源最短路径 如果图中存在退出，返回false */
    
    bool SPFA(int v){ 
    	for(int i=1;i<=n;i++)dist[i]=INF;//将最短距离初始化
    	queue<int>q;//存放顶点的队列
    	int cnt[maxn]={ 0};//记录顶点加入队列的次数，大于顶点个数，则存在负环，返回false
    	bool flag[maxn]={ false};//标记顶点是否在队列中
    	q.push(v);//将源点放入队列中
    	flag[v]=true;//标记
    	cnt[v]++;
    	dist[v]=0;
    	while(!q.empty()){ 
    		int j = q.front();
    		q.pop();
    		flag[j]=false;//取消标记
    		for(int i=1;i<=n;i++){ 
    			if(g[j][i]+dist[j]<dist[i]){ //松弛操作
    				dist[i]=g[j][i]+dist[j];
    				if(!flag[i]){ //如果该点不在队列
    					flag[i]=true;
    					cnt[i]++;
    					if(cnt[i]>n)return false;
    					q.push(i);
    				}
    			}
    		}
    	}
    	return true;
    }//
    
    int main(){ 
    	int m;
    	int a,b,c;
    	scanf("%d%d",&n,&m);
    	init();
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d%d",&a,&b,&c);
    		g[a][b]=g[b][a]=c;
    	}
    	if(SPFA(1)){ 
    		for(int i=1;i<=n;i++){ 
    			printf("%d ",dist[i]);
    		}
    	}else{ 
    		printf("该图存在负环");
    	}
    }

## 测试输入 ##

//测试一
    4 4
    1 2 2
    1 3 10 
    2 3 5
    2 4 1
    // 测试二
    4 4
    1 2 2
    1 3 10 
    2 3 -5
    2 4 1

## 测试输出 ##

//测试一
    0 2 7 3 
    // 测试二
    该图存在负环

## 参考博客 ##

[SPFA算法][SPFA]

# Floyd #

#include<bits/stdc++.h>
    using namespace std;
    
    
    /* **求所有点的最短路径（Floyd）**。 利用动态规划的思想 能够一次性求所有结点之间的最短距离； Floyd的复杂度很高，O(n^3)只能用于小规模图（你n<200) 能处理有负权边的图 负圈：带负权边的图，图中可能有这样的环路，环路上边的权值之和为负数，这样的环路就是负圈。 每走一次这个负圈，总权值就会更小，导致陷在这个圈里出不来。 用Floyd算法判断负圈：判断是否存在某个graph[i][i] < 0，就行了。 因为graph[i][i]是i到外面绕一圈回来的最小路径，如果小于0，说明存在负圈。 */
    const int maxn =1e2+3;
    int g[maxn][maxn];//利用邻接矩阵存储图结构
    int n,m;//点数，边数
    const int INF = 1<<30;//表示两点之间不存在边
    
    void init(){ 
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)g[i][j]=INF;
    }
    
    void floyd(){ 
    	int s = 1;
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    		if(g[i][k]!=INF)//在一些问题的一个优化
    			for(int j=1;j<=n;j++)if(g[i][j]>g[i][k]+g[k][j])
    			g[i][j]=g[i][k]+g[k][j];
    }
    
    
    int main(){ 
    	scanf("%d%d",&n,&m);
    	init();//初始化
    	int a,b,w;
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d%d",&a,&b,&w);
    		g[a][b]=g[b][a]=w;
    	}
    	floyd();
    }

# Bellman-Ford #

#include<bits/stdc++.h>
    using namespace std;
    
    
    /* **Bellman-Ford算法**。 单源最短路径问题：给定一个起点s，求它到图中所有n个结点的最短路径。 判断负圈：如果超过n轮，最短路径还有变化，那么肯定有负圈。 */
    const int maxn =1e5+3;
    const int INF = 1<<30;
    struct edge{ int u,v,w;}e[10005];//u->v,权重w
    int n,m;
    int pre[maxn];//记录前驱节点，用于输出路径
    int dist[maxn];//距离
    
    void path(int s,int t){ 
    	if(s==t){ printf("%d ",s);return ;}//打印起点
    	path(s,pre[t]);//先打印前一节点
    	printf(" %d",t);
    }
    
    void bellman(int s=1){ 
    	for (int i=1;i<=n;++i)dist[i]=INF;
    	dist[s]=0;
    	for(int i=1;i<=n;++i){ 
    		for(int j=0;j<m;++j){ 
    			int x=e[i].u,y=e[i].v;
    			if(dist[x]>dist[y]+e[j].w){ 
    				dist[x]=dist[y]+e[j].w;
    				pre[x]=y;
    			}
    		}
    	}
    }
    
    
    int main(){ 
    	scanf("%d%d",&n,&m);
    	int a,b,w;
    	for(int i=0;i<m;i++){ 
    		scanf("%d%d%d",&a,&b,&m);
    		int x = i<<1;
    		e[x].u=a,e[x].v=b;e[x++].w=w;
    		e[x].u=b,e[x].v=a;e[x].w=w;
    	}
    	m<<=1;
    	bellman();
    }

[SPFA]: https://blog.csdn.net/qq_40061421/article/details/82054784