洛谷题集——单源最短路径（弱化版、spfa+邻接表）

系统管理员 2023-02-21 09:03 27阅读 0赞

##### 题目 #####

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式  
第一行包含三个整数 n , m , s 分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u , v , w 表示一条u→v 的，长度为 w 的边。

输出格式  
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 231\-1

输入输出样例  
输入  
4 6 1  
1 2 2  
2 3 2  
2 4 1  
1 3 5  
3 4 3  
1 4 4  
输出  
0 2 4 3  
[洛谷测试平台][Link 1]

--------------------

*  SPFA 算法  
    Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及**判负权环**。SPFA 最坏情况下复杂度为 O(NM)。
 *  迪杰斯特拉算法  
    由荷兰计算机科学家 狄克斯特拉于1959 年提出的，因此又叫 狄克斯特拉算法。是从一个顶点到其余各顶点的 最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 迪杰斯特拉算法 最坏情况下复杂度为 O(NM)。可用堆进行优化，优化后O(( m+ n)log n)。（**不可判负权环**）

本题测试数据较小，可直接采用 spfa +邻接表解决。  
关键点

*  创建结构体数组  
    ①、存储第 i 个城市到达 s 城市的最短路径。  
    ②、存储第 i 个城市可到达的（多个）城市标号及路径长度。
 *  spfa算法——队列  
    ①、将可能为最短路径的城市插入队列中。  
    若 i 城市到 j 城市路径长度 + 第 i 城市到第 s 城市最短路径 <= j 城市到第 s 城市最短路径，则不必将 j 城市放入队列。

#include<bits/stdc++.h>
    using namespace std;
    struct node1{ 
    	int len;		//第i个城市的路径长度 
    	int end;		//通往的城市标号
    }tmp;
    
    struct node{ 
    	vector <node1> next;	//第i个城市能通往的城市信息
    	int min_dis;			//第i个城市通往s的最短路径
    }N[10010];
    
    void bfs(int a){ 
    	queue <int> q;
    	q.push(a);
    	while(!q.empty()){ 
    		int top = q.front();
    		q.pop();
    		for(int i=0; i<N[top].next.size(); i++){ 
    			int v=N[top].next[i].end;
    			//若第v个城市离s城市有更短的路径
    			//则更改第v个城市到s城市的最短路径且将v入队
    			if(N[v].min_dis>N[top].min_dis+N[top].next[i].len){ 
    				N[v].min_dis=N[top].min_dis+N[top].next[i].len;
    					q.push(v);
    			}
    		}
    	}
    }
    
    int main(){ 
    	int n, m, s;
    	cin>>n>>m>>s;
    	for(int i=1; i<=n; i++){ 
    		N[i].min_dis= (1<<31)-1;
    	}
    	
    	for(int i=0; i<m; i++){ 
    		int u, v, w;
    		cin>>u>>v>>w;
    		tmp.end=v;
    		tmp.len=w;
    		N[u].next.push_back(tmp);
    	}
    	
    	N[s].min_dis=0;
    	bfs(s);
    	
    	for(int i=1; i<=n; i++){ 
    		cout<<N[i].min_dis<<" ";
    	}
    	
    	return 0;
    }

若文章对你有帮助，可以留个赞么

[Link 1]: https://www.luogu.com.cn/problem/P3371