站长统计app软件大全,沈阳百度推广优化,在线制作名片模板,济南1951年建站题目#xff1a;
算法与数据结构实验题 10.20 迷路
★实验任务
学长经常迷路#xff0c;现在他又遇到问题了#xff0c;需要求救。
假设他有一张地图#xff0c;上面有N个点#xff0c;M条路#xff0c;他现在在编号为S的地方#xff0c;想要去编号为E的地方#x…题目
算法与数据结构实验题 10.20 迷路
★实验任务
学长经常迷路现在他又遇到问题了需要求救。
假设他有一张地图上面有N个点M条路他现在在编号为S的地方想要去编号为E的地方请你找到最短路径的长度。
好消息是每条路的长度都是1。
★数据输入
输入第一行包括四个整数NMSE。表示有N个地点M条道路CYP当前所在的地点编号为S要去的地点编号为E。
接下来M行每行两个整数uv表示地点u到地点v之间有路可以走。
★数据输出
输出一个整数表示最短的路线距离。
输入示例
5 4 1 5
1 2
2 3
3 4
4 5输出示例
4★提示
题中的图为无向图。
地点编号为1~N。
30% 1N101M20。
100% 1N1001M5000。
100% 1u,vN。
教程
程序员必会单源最短路径迪杰斯特拉算法看动画就全明白了_哔哩哔哩_bilibili
答案
代码写的很烂。。。
#include iostream
#include limits
#include vector
const int INF 0x3f3f3f3f;//最大值
using namespace std;
// 思路总结选择一个点作为起始点
// 先将这个点作为中间结点根据它直接连接的边作为更新数据更新从顶点到其他顶点的距离
// 寻找与起始距离最近且没有作为中间结点的结点以该结点作为中间节点重复步骤2
// 注意更新的时候注意连接的其他节点未被标记且更新后的路径更短
// 直到全部顶点都作为了中间节点 并且完成路径更新算法就结束了
vectorint Dijkstra(vectorvectorint graph, int start) {int n graph.size(); // 存储图中的顶点个数vectorint visit(n, 0); // 标记已作为中间节点完成访问的顶点vectorint dist(n, INF); // 存储从起点start到其他顶点的最短路径for (int i 0; i n; i) {dist[i] graph[start][i]; // 将dis数组初始化为图中的路径长度。}visit[start] 1; // 标记起始顶点// 每次添加一个点为中间节点,添加n-1次for (int i 1; i n - 1; i) {// 在dist里寻找与起始距离最近且没有被访问过的顶点,作为中间节点int min INF;int midIndex 0;for (int j 0; j n; j) {if (min dist[j] visit[j] 0 j!start) {min dist[j];minIndex j;}}visit[midIndex] 1;// 根据这个点所连接的边来更新数据更新起点到其他顶点的距离也就是更新dist数组// 先记录下起点到这个点的距离以便后序更新int distantToMid dist[midIndex];// 开始根据graph更新dist数组 for (int j 0; j n; j) {int newDist distantToMid graph[minIndex][j];//注意更新的时候该结点未被标记为中间节点且更新后的值要小于更新前的值 if(graph[minIndex][j]!INFvisit[j]!1(newDistdist[j]))dist[j] newDist;}}return dist;
}
int main() {int n, m, s, e;cin n m s e;vectorvectorint graph(n, vectorint(n));// 都先初始化为无穷大for (int i 0; i n; i) {for (int j 0; j n; j) {graph[i][j] INF;}}// 输入各点的距离,创建邻接矩阵 for (int i 0; i m; i) {int u, v;cin u v;graph[u-1][v-1] 1;graph[v-1][u-1]1;}// 调用迪杰斯特拉算法vectorint distDijkstra(graph, s-1);cout dist[e-1];
}
