算法与数据结构--最短路径Dijkstra算法

news/2024/10/31 2:20:26/

题目:

算法与数据结构实验题 10.20 迷路

★实验任务

学长经常迷路,现在他又遇到问题了,需要求救。

假设他有一张地图,上面有N个点,M条路,他现在在编号为S的地方,想要去编号为E的地方,请你找到最短路径的长度。

好消息是,每条路的长度都是1。

★数据输入

输入第一行包括四个整数N,M,S,E。表示有N个地点,M条道路,CYP当前所在的地点编号为S,要去的地点编号为E。

接下来M行每行两个整数u,v表示地点u到地点v之间有路可以走。

★数据输出

输出一个整数表示最短的路线距离。

输入示例

5 4 1 5
1 2
2 3
3 4
4 5

输出示例

4

★提示

题中的图为无向图。

地点编号为1~N。

30% 1<=N<=10,1<=M<=20。

100% 1<=N<=100,1<=M<=5000。

100% 1<=u,v<=N。

教程

程序员必会,单源最短路径,迪杰斯特拉算法,看动画就全明白了_哔哩哔哩_bilibili

答案

代码写的很烂。。。

#include <iostream>
#include <limits>
#include <vector>
const int INF = 0x3f3f3f3f;//最大值 
using namespace std;
// 思路总结:选择一个点作为起始点,
// 先将这个点作为中间结点,根据它直接连接的边作为更新数据,更新从顶点到其他顶点的距离
// 寻找与起始距离最近且没有作为中间结点的结点,以该结点作为中间节点,重复步骤2,
// 注意更新的时候注意连接的其他节点未被标记且更新后的路径更短 
// 直到全部顶点都作为了中间节点, 并且完成路径更新,算法就结束了
vector<int> Dijkstra(vector<vector<int>>& graph, int start) {int n = graph.size();     // 存储图中的顶点个数vector<int> visit(n, 0);  // 标记已作为中间节点完成访问的顶点vector<int> 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]!=INF&&visit[j]!=1&&(newDist<dist[j]))dist[j] = newDist;}}return dist;
}
int main() {int n, m, s, e;cin >> n >> m >> s >> e;vector<vector<int>> graph(n, vector<int>(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;}// 调用迪杰斯特拉算法vector<int> dist=Dijkstra(graph, s-1);cout << dist[e-1];
}


http://www.ppmy.cn/news/1262718.html

相关文章

学会用bash在linux写脚本 (一)

本章主要介绍如何使用bash写脚本。 了解通配符 了解变量 了解返回值和数值运算 grep的用法是“grep 关键字 file”&#xff0c;意思是从file中过滤出含有关键字的行。 例如&#xff0c;grep root /var/log/messages&#xff0c;意思是从/var/log/messages 中过滤出含有root …

3D点云:平面模型上提取凸(凹)多边形方法

目录 一、实现原理 二、实现代码 三、运行结果 一、实现原理 首先要在点云中提取出潜在平面,对原始点云数据进行滤波,根据提取出的平面模型系数从滤波后的点云进行投影,然后根据投影后的点云计算其对应的二维凹(凸)多边形。 二、实现代码 #in

Springboot+FastJson实现解析第三方http接口json数据为实体类(时间格式化转换、字段包含中文)

场景 若依前后端分离版手把手教你本地搭建环境并运行项目&#xff1a; 若依前后端分离版手把手教你本地搭建环境并运行项目_前后端分离项目本地运行-CSDN博客 在上面搭建SpringBoot项目的基础上&#xff0c;并且在项目中引入fastjson、hutool、lombok等所需依赖后。 系统需…

Qt内存管理、UI编辑器、客制化组件、弹出对话框、常用部件类

头文件的小技巧 #include <QtWidgets> // 在自动生成的 .h 里面加上此句 适用条件&#xff1a; QT 的内存管理 当父窗体被关闭时&#xff0c;子部件的内存会自动释放。 对象树是一种管理对象生命周期的机制。当一个对象被添加到另一个对象的子对象列表中时&#xff0…

maven环境搭建

maven历史版本下载&#xff1a;https://archive.apache.org/dist/maven/ 新建系统变量编辑Path&#xff0c;添加bin目录mvn -v测试查看版本号conf目录下新建repository文件夹&#xff0c;作为本地仓库 settings.xml <?xml version"1.0" encoding"UTF-8&…

权威认证!景联文科技入选杭州市2023年第二批省级“专精特新”中小企业认定名单

为深入贯彻党中央国务院和省委省政府培育专精特新的决策部署&#xff0c;10月7日&#xff0c;杭州市经济和信息化委员会公示了2023年杭州“专精特新”企业名单&#xff08;第二批&#xff09;。 根据工业和信息化部《优质中小企业梯度培育管理暂行办法》&#xff08;工信部企业…

【模型量化】神经网络量化基础及代码学习总结

1 量化的介绍 量化是减少神经网络计算时间和能耗的最有效的方法之一。在神经网络量化中&#xff0c;权重和激活张量存储在比训练时通常使用的16-bit或32-bit更低的比特精度。当从32-bit降低到8-bit&#xff0c;存储张量的内存开销减少了4倍&#xff0c;矩阵乘法的计算成本则二…

Java网络编程-深入理解BIO、NIO

深入理解BIO与NIO BIO BIO 为 Blocked-IO&#xff08;阻塞 IO&#xff09;&#xff0c;在 JDK1.4 之前建立网络连接时&#xff0c;只能使用 BIO 使用 BIO 时&#xff0c;服务端会对客户端的每个请求都建立一个线程进行处理&#xff0c;客户端向服务端发送请求后&#xff0c;…