区块链技术博客
www.b2bchain.cn

二十五、求单点的最短路径

这篇文章主要介绍了二十五、求单点的最短路径的讲解,通过具体代码实例进行20058 讲解,并且分析了二十五、求单点的最短路径的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20058

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

二十五、求单点的最短路径

文章目录

  • 二十五、求单点的最短路径
    • 题目描述
    • 解题思路
    • 上机代码

题目描述

求从指定源点出发到各个顶点的最短路径。

二十五、求单点的最短路径

**假设:**图中结点名均为单个互不相同的字母,权值均>0。

输入:
第一行:结点数量n,弧数量e,源点
后续e行:<结点,结点,权值>

输出:
按结点的升序输出到达各个结点的最短路径长度

测试输入 期待的输出 时间限制 内存限制 额外进程
测试用例 1 7,10,a
<a,b,13>
<a,c,8>
<c,d,5>
<d,e,6>
<a,e,30>
<a,g,32>
<b,g,7>
<b,f,9>
<e,f,2>
<f,g,17>
a:0
b:13
c:8
d:13
e:19
f:21
g:20
1秒 64M 0
测试用例 2 5,9,a
<a,b,10>
<b,a,20>
<a,d,50>
<a,e,45>
<b,c,15>
<c,d,20>
<c,e,5>
<d,e,10>
<e,c,30>
a:0
b:10
c:25
d:45
e:30
1秒 64M 0
测试用例 3 5,7,a
<a,b,10>
<b,c,50>
<a,d,30>
<a,e,100>
<c,e,10>
<d,c,20>
<d,e,60>
a:0
b:10
c:50
d:30
e:60
1秒 64M 0

解题思路

在之前参加集训时,ACM集训队的同学向我们讲了四种计算最短路的算法:Floyd、Dijkstra、Bellman-Ford、SPFA。

其中,Floyd适合计算多源最短路,Dijkstra、Bellman-Ford、SPFA适合单源最短路。Dijkstra不能处理权值为负的情况,而 Bellman-Ford 可以处理负权值,SPFA是对 Bellman-Ford 的计算优化。

本题很明显可以看出是很经典的单源最短路问题,且权值均大于0,可以采用常用的 Dijkstra 算法来计算。

输入序列中的结点名并不是数字而是字母,因为我们做一个简单的减法,将结点名转换为数字,集训时已经做过很多这样的题了,直接套用之前总结好的板子就可以了。

上机代码

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int inf = 0x3f3f3f; int road[1010][1010], d[1010]; bool vis[1010]; int n, m, num = 0;  void dijkstra(int s)//dijkstra算法 { 	for (int i = 0; i < n; i++) 	{ 		d[i] = road[s][i]; 		vis[i] = false; 	} 	d[s] = 0; 	vis[s] = true; 	for (int i = 0; i < n; i++) 	{ 		int temp = inf, v; 		for (int j = 0; j < n; j++) 		{ 			if (!vis[j] && temp > d[j]) 			{ 				temp = d[j]; 				v = j; 			} 		} 		if (temp == inf) 			break; 		vis[v] = true; 		for (int j = 0; j < n; j++) 		{ 			if (!vis[j] && d[v] + road[v][j] < d[j]) 			{ 				d[j] = d[v] + road[v][j]; 			} 		} 	} } int main() { 	int x, y, dis; 	char a, b, c; 	scanf("%d,%d,%c", &m, &n, &c); 	getchar();					//读取换行符 	for (int i = 0; i < n; i++)//初始化 	{ 		for (int j = 0; j < n; j++) 		{ 			road[i][j] = (i == j) ? 0 : inf; 		} 	} 	for (int i = 0; i < n; i++) 	{ 		scanf("<%c,%c,%d>", &a, &b, &dis); 		getchar(); 		x = a - 'a';//把字符转化为数字来算 		y = b - 'a'; 		if(road[x][y]>dis) 			road[x][y]= dis; 	} 	num = c - 'a'; 	dijkstra(num); 	for (int i = 0; i < m; i++) 	{ 		printf("%c:%dn", i + 'a', d[i]);//记得转回字符 	} 	//system("pause"); 	return 0; } 

本文转自互联网,侵权联系删除二十五、求单点的最短路径

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 二十五、求单点的最短路径
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们