精华内容
下载资源
问答
  • 单源最短路径

    2021-02-28 14:02:05
    单源最短路径 单源最短路径问题,给定一个图G=(V,E),找出从给定的源点s∈V到其它每个结点v∈V的最短路径。 这里主要记录了三种算法:dijkstra: 贪心, Floyd: 动归 (Spfa:它没了) 洛谷链接: P3371 【模板】单源...

    单源最短路径

    单源最短路径问题,给定一个图G=(V,E),找出从给定的源点s∈V到其它每个结点v∈V的最短路径。

    这里主要记录了三种算法:dijkstra: 贪心, Floyd: 动归 (Spfa:它没了)

    洛谷链接:

    P3371 【模板】单源最短路径(弱化版) : ford无法通过,SPFA和Dijkstra可通过

    P4779 【模板】单源最短路径(标准版):只有Dijkstra可通过

    0. 一些说明

    0.1 初始化

    69tS78.png

    在开始各种单源最短路径之前,都需要预先对节点进行初始化,对于每个节点v,维持一个属性v.d,记录从源节点s到节点v的最短路径长度,v.Π记录其前驱节点

    0.2 松弛操作

    69t139.png

    所有的单源最短路径算法都需要使用到松弛操作

    松弛操作是对于一条从节点u到节点v的权重为w的一条边,将从结点s到结点u之间最短路径加上结点uv之间的边的权重,然后与当前的sv的最短路径估计v.d进行比较,看有没有变小。如果变小,则对v.dv.π进行更新,这一操作就称为“松弛”

    1. Bellman-ford算法

    可以有负权重的边,但不能有负权重的环

    696F9x.png

    因为总共只有|V|个节点,且不存在负权重的环,所以从s出发,通过|V| - 1步一定能到达所有能到达节点,并且通过不断的松弛操作,就能或得从s出发的所有最短路径了。算法复杂度就是O(VE)O(VE)

    举个栗子

    69cEin.png

    代码部分:

    #include<iostream>
    #include<string.h>
    using namespace std;
    #define N 110
    #define M 5100
    int edge[M][3], ans[N];	// 存储边
    int main() {
    	memset(ans, 127, sizeof(ans));	// 将目标点距离设置为最大值
    	int n, m, s;
    	cin >> n >> m >> s;
    	ans[s] = 0;
    	for (int i = 0; i < m; i++) {
    		cin >> edge[i][0] >> edge[i][1] >> edge[i][2];	// 记录每一条边
    	}
    	for (int i = 0; i < n - 1; i++) {	// 遍历n - 1遍
    		for (int j = 0; j < m; j++) {	// 遍历所有的边
    			if (ans[edge[j][0]] != 2139062143 && \
    				ans[edge[j][1]] > ans[edge[j][0]] + edge[j][2])	// relax操作
    				ans[edge[j][1]] = ans[edge[j][0]] + edge[j][2];
    		}
    	}
    	// 输出结果
    	for (int i = 1; i <= n; i++) {
    		if (ans[i] == 2139062143)	// 说明s不能到达该节点
    			cout << "2147483647 ";
    		else
    			cout << ans[i] << " ";
    	}
    	return 0;
    }
    

    2. SPFA算法

    参考链接:链接1链接2

    SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,算法复杂度为O(kE)O(kE), k是一个常数,指每个点平均进队次数(在稀疏图中k较小,在稠密图中k较大),因此算法稳定性较差。

    但是至少不会比Bellman-ford差,同时也能应对负权重的情况(Dijkstra不行),并且可以用于检测负环,洛谷链接:模板:负环

    实现过程:

    1. 存入图,一般使用链式前向星
    2. 创建一个队列,将起始节点放入队列
    3. 每次从队列中取出一个节点x,遍历所有和x相邻的节点y,然后进行松弛操作,如果能进行松弛操作,则将节点y也加入到队列中(如果已在队列中则不需要重复加入),这个期间中可以记录节点松弛的次数,如果松弛次数大于n-1次,就说明图中有负环。

    SPFA的模拟过程可以参考链接2

    代码部分:

    #include<iostream>
    #include<string.h>
    #include<queue>
    using namespace std;
    #define N 110
    #define M 5100
    struct edge	// 边
    {
    	int to, next, w;
    }arr[M];
    int head[N], length = 1, ans[N];
    void add(int u, int v, int w) {	// 链式前向星
    	arr[length].to = v;
    	arr[length].w = w;
    	arr[length].next = head[u];
    	head[u] = length;
    	length++;
    	}
    void spfa(int n, int m, int s) {
    	int temp;
    	queue<int> q;
    	bool flag[N];	// 用于记录是否位于队列中
    	memset(flag, 0, sizeof(flag));
    	q.push(s);	// 将起始节点装入队列
    	ans[s] = 0;	// 起始节点距离为0
    	flag[s] = true;	// 标记起始节点在队列中
    	while (!q.empty()) {
    		temp = q.front();	// 取出队首元素
    		q.pop();
    		flag[temp] = false;	// temp不在队列中了
    		for (int i = head[temp]; i != 0; i = arr[i].next) {
    			if (ans[arr[i].to] > ans[temp] + arr[i].w) {	// 松弛操作
    				ans[arr[i].to] = ans[temp] + arr[i].w;
    				if (!flag[arr[i].to]) {	// 如果不在队列中
    					q.push(arr[i].to);
    				}
    			}
    		}
    	}
    }
    int main() {
    	int n, m, s, u, v, w;
    	memset(head, 0, sizeof(head));
    	memset(ans, 127, sizeof(ans));
    	cin >> n >> m >> s;
    	for (int i = 0; i < m; i++) {
    		cin >> u >> v >> w;
    		add(u, v, w);
    	}
    	spfa(n, m, s);
    	for (int i = 1; i <= n; i++) {
    		if (ans[i] == 2139062143)
    			cout << "2147483647 ";
    		else
    			cout << ans[i] << " ";
    	}
    	return 0;
    }
    

    3. Dijkstra算法

    该算法要求所有边的权重均为非负值!

    69Wpfs.png

    模拟一下这个过程:

    69Wfcq.png

    代码部分:

    #include<iostream>
    #include<map>
    #include<queue>
    #include<string.h>
    using namespace std;
    #define N 1100
    #define M 2100
    struct edge
    {
    	int to, next, w;
    }arr[M];
    int head[N], length = 1, ans[N];
    bool vis[N];
    void add(int u, int v, int w) {	// 链式前向星
    	arr[length].to = v;
    	arr[length].w = w;
    	arr[length].next = head[u];
    	head[u] = length;
    	length++;
    }
    void dijkstra(int n, int m, int s) {
    	int temp, cnt = 0;
    	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;	// 优先队列
    	ans[s] = 0;
    	q.push(make_pair(0, s));
    	while (!q.empty() && cnt < n) {
    		temp = q.top().second;	// 取出最小节点
    		q.pop();
    		if (vis[temp])
    			continue;	// 每个节点只访问一遍
    		vis[temp] = true;
    		cnt++;	// 已访问节点个数,当cnt = n时可以提前结束循环,而不需要队列为空
    		for (int i = head[temp]; i != 0; i = arr[i].next) {	// 遍历该节点的所有相邻边
    			if (vis[arr[i].to])
    				continue;
    			else if(ans[arr[i].to] > ans[temp] + arr[i].w){
    				ans[arr[i].to] = ans[temp] + arr[i].w;
    				q.push(make_pair(ans[arr[i].to], arr[i].to));
    			}
    		}
    	}
    }
    int main() {
    	int n, m, s, u, v, w;
    	memset(head, 0, sizeof(head));
    	memset(vis, 0, sizeof(vis));
    	memset(ans, 127, sizeof(ans));
    	cin >> n >> m >> s;
    	for (int i = 0; i < m; i++) {
    		cin >> u >> v >> w;
    		add(u, v, w);
    	}
    	dijkstra(n, m, s);
    	for (int i = 1; i <= n; i++) {
    		if (ans[i] == 2139062143)
    			cout << "2147483647 ";
    		else
    			cout << ans[i] << " ";
    	}
    	return 0;
    }
    

    4. 总结

    • 没有负权重边用Djikstra
    • 有负权重边用SPFA
    • 判断是否有负环用SPFA

    😋

    展开全文
  • java实现单源最短路径

    2020-08-26 10:27:16
    主要为大家详细介绍了java实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Dijstra算法用于求解单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。
  • 经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径
  • 单源最短路径算法,包括BellmanFord算法,有向无环图中的单源最短路径算法和Dijkstra算法
  • Dijkstra算法单源最短路径搜索演示

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,817
精华内容 2,726
关键字:

单源最短路径