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

文章目录

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

题目描述

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

**假设：**图中结点名均为单个互不相同的字母，权值均>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:%d\n", i + 'a', d[i]);//记得转回字符}//system("pause");return 0; }

总结

以上是生活随笔为你收集整理的二十五、求单点的最短路径的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。