酒店手机网站首页设计世界搜索引擎大全
目录
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二、算法分析
- 从给定题目的初步分析可以看出，这是比较典型的带权图最短路径问题
- 小朋友们在解决这类题型的时候可以使用DFS+邻接矩阵的方式实现，
- 可能有些小朋友们会问，什么是邻接矩阵？
- 邻接矩阵是用来表示图的一种常用方法。如果图中有n个节点，则邻接矩阵是一个n×n的矩阵，矩阵中的每个元素aij表示节点i与节点j之间是否存在边。如果存在边，则aij的值为1或边的权重；如果不存在边，则aij的值为0或一个特定的标志值。
- 由于我们要求的是最短路径，所以可以设置邻接矩阵中对角线的值为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五、考点分析
难度级别：难，这题相对而言难在题目分析，具体主要考查如下：
- 分析题目，找到解题思路
- 充分掌握变量和数组的定义和使用
- 学会深度搜索算法的原理和使用
- 学会邻接矩阵的表示和应用
- 学会输入流对象cin的使用，从键盘读入相应的数据
- 学会for循环的使用，在确定循环次数的时候推荐使用学会
- 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
- 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
- 充分掌握变量定义和使用、分支语句、循环语句和深度搜索算法的应用
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
六、推荐资料
- 所有考级比赛学习相关资料合集【推荐收藏】