专门做金融的招聘网站,网站解析密码,做食品网站,湖州网络公司网站建设目录
C求最短路径
一、题目要求
1、编程实现
2、输入输出
二、算法分析
三、程序编写
四、运行结果
五、考点分析
六、推荐资料 C求最短路径
一、题目要求
1、编程实现
给定n个顶点#xff0c;每个顶点到其它顶点之间有若干条路#xff0c;选择每条路需要消耗一定…
目录
C求最短路径
一、题目要求
1、编程实现
2、输入输出
二、算法分析
三、程序编写
四、运行结果
五、考点分析
六、推荐资料 C求最短路径
一、题目要求
1、编程实现
给定n个顶点每个顶点到其它顶点之间有若干条路选择每条路需要消耗一定的能量问从起点出发到达最后一个点消耗的能量最少是多少
例如有5个顶点共有8条路如下图所示 2、输入输出
输入描述第一行顶点个数n和路数m1n201m200 接下来m行每行三个数分别为xyzx和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
二、算法分析
从给定题目的初步分析可以看出这是比较典型的带权图最短路径问题小朋友们在解决这类题型的时候可以使用DFS邻接矩阵的方式实现可能有些小朋友们会问什么是邻接矩阵邻接矩阵是用来表示图的一种常用方法。如果图中有n个节点则邻接矩阵是一个n×n的矩阵矩阵中的每个元素aij表示节点i与节点j之间是否存在边。如果存在边则aij的值为1或边的权重如果不存在边则aij的值为0或一个特定的标志值。由于我们要求的是最短路径所以可以设置邻接矩阵中对角线的值为0即自己到自己其它矩阵的值初始为一个极大值方便后续进行判断
三、程序编写
#includebits/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()
{cinnm;//输入n接矩阵for(int i1;in;i){for(int j1;jn;j)if(ij)grid[i][j] 0;//自己指向自己距离为0elsegrid[i][j] Maxn;//其它都初始为最大值}for(int i1;im;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 j1;jn;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
五、考点分析
难度级别难这题相对而言难在题目分析具体主要考查如下
分析题目找到解题思路充分掌握变量和数组的定义和使用学会深度搜索算法的原理和使用学会邻接矩阵的表示和应用学会输入流对象cin的使用从键盘读入相应的数据学会for循环的使用在确定循环次数的时候推荐使用学会掌握输出流对象cout的使用与流插入运算符 结合使用将对象输出到终端显示学会分析题目算法分析将复杂问题模块化简单化从中找到相应的解题思路充分掌握变量定义和使用、分支语句、循环语句和深度搜索算法的应用
PS方式方法有多种小朋友们只要能够达到题目要求即可 六、推荐资料
所有考级比赛学习相关资料合集【推荐收藏】
