算法与数据结构--最短路径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];
}