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

题目：

算法与数据结构实验题 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];
}