一、Dijkstra介绍

1、 Dijkstra是什么即解决的问题

     Dijkstra算法是一种用于解决单源最短路径问题的经典算法，Dijkstra算法是一种用于解决单源最短路径问题的经典算法（其实就是给你好几个点，然后各个点由路径连接，每个路径被赋予权值，求出原点到每个点要走的距离） 如下图所示：

这样可以得出每个点到原点的最短距离

2、 Dijkstra如何实现

1、初始化：

         我们定义dis数组来存储每个点到原点的最短距离，初始时先让每个距离都无穷大。然后我们定义一个二维数组graph来存储每条边的权值，再定义check数组存储这个点是否被遍历过

示例代码：

​
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
int main(){
    int n,e;   //n是点的数量，e是边的数量
    cin>>n>>e;
    vector<int> dis(n+1);
    vector<int> check(n+1);
    vector<vector<int>> graph(e+1,vector<int>(e+1));
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    for(int i=0;i<e;i++){
        int a,b,c;
        graph[a][b]=c;  //数组两点和距离，代表a点到b点的距离是c
    }
    
}

​

2、寻找单源最短路（核心代码）

 cin>>s;  //输入出发点
    dis[s]=0;
    for(int i=0;i<n;i++){ // 有n个点要遍历n次
        int minn=inf,minx;
        for(int j=1;j<=n;j++){
            if(dis[j]<minn&&check[j]){
                minx=j;
                minn=dis[j];
            }
        }
        for(int k=1;k<=n;k++){
            if(graph[minn][k]){
                dis[k]=min(dis[k],dis[minn]+graph[minn][k]);
                }
            }
            check[minn]=0;
    }

1. dis[s]=0;：将起始顶点的距离数组dis[]中起始顶点s的距离设为0，表示起始顶点到自身的距离为0。

2. for(int i=0;i<n;i++)：循环遍历所有顶点，其中n表示顶点的总数。

3. 内部循环：

   • int minn=inf, minx;：初始化minn为一个较大的值（这里用inf表示无穷大），minx用于记录距离起始顶点最近的顶点编号。
   • 遍历所有顶点j，如果顶点j的距离小于minn且check[j]为真（表示顶点j还未确定最短路径），则更新minn和minx为顶点j的编号和距离。

4. 更新距离：

   • 遍历所有顶点k，如果顶点minx到顶点k有边相连（graph[minx][k]非零），则更新起始顶点到顶点k的距离dis[k]为当前距离和通过顶点minx到顶点k的距禒之和的最小值。

5. check[minx]=0;：将顶点minx标记为已确定最短路径。

      这段代码实现了Dijkstra算法的核心逻辑，通过遍历所有顶点并逐步更新最短路径长度，最终可 以得到起始顶点到所有其他顶点的最短路径长度。

---

三、完整实现代码

#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
int main(){
    int n,e;   //n是点的数量，e是边的数量
    cin>>n>>e;
    vector<int> dis(n+1);
    vector<int> check(n+1,1);
    vector<vector<int>> graph(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    for(int i=0;i<e;i++){
        int a,b,c;
        graph[a][b]=c;  //数组两点和距离，代表a点到b点的距离是c
    }
    int s;
    cin>>s;  //输入出发点
    dis[s]=0;
    for(int i=0;i<n;i++){ // 有n个点要遍历n次
        int minn=inf,minx;
        for(int j=1;j<=n;j++){
            if(dis[j]<minn&&check[j]){
                minx=j;
                minn=dis[j];
            }
        }
        for(int k=1;k<=n;k++){
            if(graph[minn][k]){
                dis[k]=min(dis[k],dis[minn]+graph[minn][k]);
                }
            }
            check[minn]=0;
    }
    return 0;
}

---

四、如何解决数据规模较大，开邻接表

  用vector数组去开邻接表

1、邻接表的初始化 

    vector<vector<pair<int, int>>> adjList(n + 1); // 邻接表，下标从1开始

    int m; // 边数
    cin >> m;

    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的起点、终点和权重
        cin >> u >> v >> w;
        adjList[u].push_back({v, w}); // 无向图
        adjList[v].push_back({u, w}); // 若为有向图则只需一行
    }

2、邻接表的遍历

    for (int i = 1; i <= n; ++i) {
        cout << "顶点 " << i << " 的邻居: ";
        for (auto neighbor : adjList[i]) {
            cout << neighbor.first << "(" << neighbor.second << ") ";
        }
        cout << endl;
    }

    return 0;
}