算法学习018 求最短路径 c++算法学习 中小学算法思维学习 比赛算法题解 信奥算法解析

目录

C++求最短路径

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、运行结果

五、考点分析

六、推荐资料

---

C++求最短路径

一、题目要求

1、编程实现

给定n个顶点，每个顶点到其它顶点之间有若干条路，选择每条路需要消耗一定的能量，问从起点出发到达最后一个点消耗的能量最少是多少

例如：有5个顶点，共有8条路，如下图所示：

2、输入输出

输入描述：第一行顶点个数n和路数m（1<=n<=20，1<=m<=200）

                  接下来m行，每行三个数，分别为x，y，z；x和y为顶点，z为x到y所消耗的能量

输出描述：只有一行，一个整数，即从起点出发到达最后一个点消耗的最小能量

输入样例：

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

输出样例：

9

二、算法分析

1. 从给定题目的初步分析可以看出，这是比较典型的带权图最短路径问题
2. 小朋友们在解决这类题型的时候可以使用DFS+邻接矩阵的方式实现，
3. 可能有些小朋友们会问，什么是邻接矩阵？
4. 邻接矩阵是用来表示图的一种常用方法。如果图中有n个节点，则邻接矩阵是一个n×n的矩阵，矩阵中的每个元素aij表示节点i与节点j之间是否存在边。如果存在边，则aij的值为1或边的权重；如果不存在边，则aij的值为0或一个特定的标志值。
5. 由于我们要求的是最短路径，所以可以设置邻接矩阵中对角线的值为0（即自己到自己），其它矩阵的值初始为一个极大值（方便后续进行判断）

三、程序编写

#include<bits/stdc++.h>
using namespace std;
const int Maxn = INT_MAX;//limits.h头文件
int mindis = Maxn,grid[101][101],visited[101];//mindis最短距离，gird二维矩阵，visited已经访问过
int n,m,x,y,z;	//n行  m条边，x、y为顶点，z为它们的距离
void dfs(int,int);int main()
{cin>>n>>m;//输入n接矩阵for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(i==j)grid[i][j] = 0;//自己指向自己距离为0elsegrid[i][j] = Maxn;//其它都初始为最大值}for(int i=1;i<=m;i++){//输入每条边及对应的距离cin >> x >> y >> z;grid[x][y] = z;}//从第一个点开始进行搜索visited[1] = 1;dfs(1,0);cout << mindis;return 0;
}
//深度搜索从当前点开始进行搜索，直到到达最后一个顶点
void dfs(int cur,int dis)
{if(cur == n){mindis = min(mindis,dis);//返回最短距离return;}for(int j=1;j<=n;j++){//矩阵中的值不是最大值，说明有路径可以走，同时访问的点是未访问过的if(grid[cur][j] != Maxn && !visited[j]){visited[j] = 1;//标记访问dfs(j,dis + grid[cur][j]);//继续下一个顶点深搜，距离为当前距离加上路径上的权值visited[j] = 0;//回溯访问标记}}
}

 本文作者：小兔子编程 作者首页：小兔子编程-CSDN博客

四、运行结果

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 39

五、考点分析

难度级别：难，这题相对而言难在题目分析，具体主要考查如下：

1. 分析题目，找到解题思路
2. 充分掌握变量和数组的定义和使用
3. 学会深度搜索算法的原理和使用
4. 学会邻接矩阵的表示和应用
5. 学会输入流对象cin的使用，从键盘读入相应的数据
6. 学会for循环的使用，在确定循环次数的时候推荐使用学会
7. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
8. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
9. 充分掌握变量定义和使用、分支语句、循环语句和深度搜索算法的应用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

六、推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】