題目：

算法與數據結構實驗題 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];
}