#创作计划#迪杰斯特拉算法精讲

‮༺དༀ༒∞░∞༒ༀཌ༻

2025-10-19 09:50:21

发布于：浙江

616阅读

0回复

0点赞

！！！

不是这玩意咋上榜的

$\huge{第零篇？}$

----------------------------------------------------第一篇----------------------------------------------------------

前言：

可能更好的学习体验？

本文适合深色模式食用

本帖分为三个部分，

1.算法讲解

2.代码解析

3.真题演练

作者的话：

额，被老师逼迫了，所以来写帖子 ~~顺便水个精华帖~~ 。我会写四篇帖子。三篇是单源最短路，一篇是全源最短路。这是第一篇迪杰斯特拉。我觉得只讲思路和代码，不讲例题就不是一篇好的精华帖，所以，这个帖子被分为了三个部分，算法讲解，代码分析和真题演练。作者还苦修了一国庆的markdowm排版，大家可以评价一下这一篇帖子。嗯，我觉得可以给个头秃（虽然不是比赛）：
忘穿秋裤的回复套路，可以发现没有剪辑的痕迹，所以你懂得：

事实上忘穿秋裤已经被榨干了（bushi

正文：

第一部分，算法讲解。

先来讲讲迪杰斯特拉的创作背景吧。（内容参考了AI总结）：
迪杰斯特拉在 $1956$ - $1959$ 年设计该算法时，主要目的是解决荷兰东部城市鹿特丹到格罗宁根的汽车路线规划问题。这一需求推动了算法的诞生，其核心在于通过贪心策略和优先队列优化实现高效路径计算。 ‌
迪杰斯特拉是求单源最短路径的一个算法，整体采用了 $\color{red}贪心$ 的策略。该算法可以通过优先队列进行优化，本帖只讲他未优化的用邻接矩阵实现的算法（其实是不会写优化(doge）。如果不知道邻接矩阵怎么写可以在帖子下方评论，我会考虑写一个简单的邻接矩阵的讲解，但是就不标创人计划了。
先口胡口头讲解一下。从起点出发，首先将起点设为 $0$ ,其他点设为无限^[1]。将当前点标记为已走过，遍历当前节点的相邻点，我们可以计算出：
设 $k$ 为当前节点的最短路径， $w$ 为遍历到此节点所计算出的路径，该节点这一轮遍历的结果为：

$min(k,w)$

遍历完所有相邻点时，我们在其相邻节点中选择路径最短的点，重复上述操作，知道所有节点遍历完成。迪杰斯特拉算法的时间复杂度是 $O(n^2)$ 。需要特别注意，迪杰斯特拉算法 $\color{red}无法$ 处理负权边^[2]，具体原因见我下面的讲解。

注：红色部分为初始化内容，其余部分为正式遍历

$\color{red}1.$ 好的，保留节目，我画了一个简单的有向图，用于模拟迪杰斯特拉算法的实现过程。同时，我直接按照上面我讲的初始化了。同时，为了防止你们眼睛x掉，我特意用了3天换了个材质

$\color{red}2.$ 从起点开始，初始化^[3]。输入这个图，构建邻接矩阵。

正式开始遍历。先从节点 $A$ 开始遍历，A的邻居顶点有 $B$ 和 $C$ 。从 $A$ 到 $B$ 的距离为 $2$ ，因为 $2 < 无穷$ , 所以我们把 $dis$ 数组中 $B$ 的位置设为 $2$ 。按照上述操作，将 $dis$ 数组中的 $C$ 设为 $5$ 。
如图，可得 $A$ 相邻的节点中， $B$ 的距离是最短的，所以我们从节点 $A$ 开始遍历节点 $B$ 。

按照上述方法遍历节点 $B$ 的相邻节点。当前节点路径长度为前一个节点的路径长度加上边的权值。所以我们可得在 $dis$ 数组中， $D$ 的数值为 $3$ ， $E$ 的数值为 $8$ 。同时，将节点 $B$ 设为已访问。

3. 这样节点 $B$ 的遍历就完成了。在 $dis$ 数组中寻找未访问且当前路径最短的节点，可以发现是节点 $D$ 。那么我们从节点 $B$ 到节点 $D$ 。

4.更新节点 $D$ 的所有邻居节点的当前最短路径。这里不详细解释了。同时记得把 $D$ 标记为已访问。

5.可以发现节点 $E$ 的最短路径从 $8$ 变为了 $4$ 。节点 $F$ 的最短路径从无穷变为了 $9$ 。那么节点 $D$ 就遍历完成了。寻找路径最短且未被访问过的顶点，为节点 $E$ 。那么从节点 $E$ 开始访问。这里不做详细解释。

6.顶点 $G$ 的最短路径从无穷变为了 $14$ 。选择当前路径最短且未访问的顶点 $C$ 。 $C$ 没有邻居，将 $C$ 设为已访问。寻找下一个符合要求的节点，为节点 $F$ 。

7.从节点 $F$ 开始遍历，节点 $G$ 的最短路径从 $14$ 变为了 $10$ 。

8.最后访问终点 $G$ 。没有可访问的节点。那么该图的迪杰斯特拉算法结束。通过 $dis$ 数组可得每个节点的在最短路径。

第二部分：代码解析：

首先我们要初始化。详见^[3:1]。

for(int i=0;i<=n;i++){
    dis[i]=N;
}dis[s]=0;

接下来开始遍历所有节点，这是一个大 $for$ 循环。我们先选择当前所要遍历的节点 $u$ 。

int u=0;
for(int j=1;j<=n;++j){
    if(!vis[j] and dis[j] < dis[u])u=j;
}vis[u]=1;

开始遍历 $u$ 的邻居节点。如果有这个节点，我们更新^[4]该节点。

for(int j=1;j<=n;j++){//遍历检查所有点
    if(mp[u][j]){//如果u到j点有边
        int w = mp[u][j];//获取u点到j点的距离
            if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                dis[j]=dis[u]+w;//将到j点的距离数组更新。
            }
    }
}

综上所述，迪杰斯特拉的核心代码为：

for(int i=1;i<=n;i++){
    int u=0;//认为当前距离最短的点为0
    for(int j=1;j<=n;++j){
        if(!vis[j] and dis[j] < dis[u])u=j;//如果这个点没有选定且当为j点的距离比u的距离更短，对最短路径u点更新
    }vis[u]=1;//选定了u点，对u点进行标记
    for(int j=1;j<=n;j++){//遍历检查所有点
        if(mp[u][j]){//如果u到j点有边
            int w = mp[u][j];//获取u点到j点的距离
            if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                dis[j]=dis[u]+w;//将到j点的距离数组更新。
            }
        }
    }
}

最后，整体代码：

//迪杰斯特拉，邻接矩阵实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=0x3f3f3f3f;
int mp[1005][1005];
int n,m,s;
int ans;
int dis[1005]={-1},vis[1005];
//迪杰斯特拉函数
void dij(int n,int s){
    //将所有的点距离设置为无穷
    for(int i=0;i<=n;i++){
        dis[i]=N;
    }dis[s]=0;//s为起点，s到s的点的距离为0
    //遍历所有的点
    for(int i=1;i<=n;i++){
        int u=0;//认为当前距离最短的点为0
        for(int j=1;j<=n;++j){
            if(!vis[j] and dis[j] < dis[u])u=j;//如果这个点没有选定且当为j点的距离比u的距离更短，对最短路径u点更新
        }vis[u]=1;//选定了u点，对u点进行标记
        for(int j=1;j<=n;j++){//遍历检查所有点
            if(mp[u][j]){//如果u到j点有边
                int w = mp[u][j];//获取u点到j点的距离
                if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                    dis[j]=dis[u]+w;//将到j点的距离数组更新。
                }
            }
        }
    }
}
signed main(){
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        
        int tmp=mp[u][v]?mp[u][v]:N;//邻接矩阵储存图，如果该位置，没有边则设置为无限（既0x3f3f3f3f）。否则为原本的边与当前边的较小者。
        mp[u][v]=min(tmp,w); //人话就是处理重边
    }dij(n,s);//函数调用，n为点的个数，s为起点
    for(int i=1;i<=n;i++){//依次输出所有点从起点s的最短路径
        if(dis[i]==N)cout << -1 << " "; //不能到达则输出-1
        else cout << dis[i] << " ";//能到达输出最短路径
    } 
    return 0;
}

第三部分，真题演练。

先看题。

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让 SPFA 不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 $n,m,s$ ，分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$ ，表示一条 $u \to v$ 的，长度为 $w$ 的边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$ 。

输入输出样例 #1

输入 #1

输出 #1

0 2 4 3

说明/提示

【数据范围】
对于 $20\%$ 的数据： $1\le n \le 5$ ， $1\le m \le 15$ ；
对于 $40\%$ 的数据： $1\le n \le 100$ ， $1\le m \le 10^4$ ；
对于 $70\%$ 的数据： $1\le n \le 1000$ ， $1\le m \le 10^5$ ；
对于 $100\%$ 的数据： $1 \le n \le 10^4$ ， $1\le m \le 5\times 10^5$ ， $1\le u,v\le n$ ， $w\ge 0$ ， $\sum w< 2^{31}$ ，保证数据随机。

Update 2022/07/29：两个点之间可能有多条边，敬请注意。

对于真正 $100\%$ 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

图片 1 到 3 和 1 到 4 的文字位置调换。

这道题我们的代码是过不了的。事实上，你提交的时候只会得70分或60分。因为正解是邻接表。
很简单，板子题。

//这是迪杰斯特拉的板子
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=0x3f3f3f3f;
int mp[9005][9005];
int n,m,s;
int ans;
int dis[1005]={},vis[1005];
void dij(int n,int s){
    //将所有的点距离设置为无穷
    for(int i=0;i<=n;i++){
        dis[i]=N;
    }dis[s]=0;//s为起点，s到s的点的距离为0
    //遍历所有的点
    for(int i=1;i<=n;i++){
        int u=0;//认为当前距离最短的点为0
        for(int j=1;j<=n;++j){
            if(!vis[j] and dis[j] < dis[u])u=j;//如果这个点没有选定且当为j点的距离比u的距离更短，对最短路径u点更新
        }vis[u]=1;//选定了u点，对u点进行标记
        for(int j=1;j<=n;j++){//遍历检查所有点
            if(mp[u][j]){//如果u到j点右有边
                int w = mp[u][j];//获取u点到j点的距离
                if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                    dis[j]=dis[u]+w;//将到j点的距离数组更新。
                }
            }
        }
    }
}
signed main(){
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        
        int tmp=mp[u][v]?mp[u][v]:N;
        mp[u][v]=min(tmp,w); 
    }dij(n,s);
    for(int i=1;i<=n;i++){
        if(dis[i]==N)cout << (int)pow(2,31)-1 << " "; 
        else cout << dis[i] << " ";

    }return 0;
}

再看一道。

题目和上面一样，不过变成了无向图。这里就不搬了。
那么无向图怎么做？
和有向图一样。 $dis$ 函数是不变的。但是，在输入的时候我们要考虑这一问题。可以发现在邻接矩阵中，无向图会有两边的储存。比如 mp[u][v] 与 mp[v][u] 是一样的。但是有向图中这两个位置的值有一个是 $0$ 。所以我们只要输入双向边即可。这里做了重边处理：

#include <bits/stdc++.h>
using namespace std;
int mp[1005][1005];
int n,m,s;
int ans;
int dis[1005]={-1},vis[1005];
void dij(int n,int s){
    //将所有的点距离设置为无穷
    for(int i=0;i<=n;i++){
        dis[i]=0x3f3f3f3f;
    }dis[s]=0;//s为起点，s到s的点的距离为0
    //遍历所有的点
    for(int i=1;i<=n;i++){
        int u=0;//认为当前距离最短的点为0
        for(int j=1;j<=n;++j){
            if(!vis[j] and dis[j] < dis[u])u=j;//如果这个点没有选定且当为j点的距离比u的距离更短，对最短路径u点更新
        }vis[u]=1;//选定了u点，对u点进行标记
        for(int j=1;j<=n;j++){//遍历检查所有点
            if(mp[u][j]){//如果u到j点右有边
                int w = mp[u][j];//获取u点到j点的距离
                if(dis[j]>dis[u]+w){//检查如果u点到j点的距离，小于原本j点的距离
                    dis[j]=dis[u]+w;//将到j点的距离数组更新。
                }
            }
        }
    }
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        
        int tmp=mp[u][v]?mp[u][v]:0x3f3f3f3f;
        mp[u][v]=mp[v][u]=min(tmp,w); 
        
    }dij(n,1);
    for(int i=2;i<=n;i++){
        if(dis[i]==0x3f3f3f3f)cout << 1000000000 << endl; 
        else cout << dis[i] << endl;

    } 
    return 0;
}

那么本帖就到这里结束了，谢谢各位的观看

本贴如有错误，请私信贴主。

彩蛋：

$\huge{第二篇}$ 第二篇→

注解：

在c++中，无限可以用0x3f3f来表示，你可以不断地加上3f，但是建议你叠加时不要超过八个3f（即0x3f3f3f3f3f3f3f3f ），在往上叠加就没用了，而且可能会CE。 ↩︎
即边的权值为负的边 ↩︎
将$ dis$ 数组中除起点外的其他点设为无穷，起点设为 $0$ 。 $vis$ 数组中讲起点设为 $1$ ，其余点设为 $0$ 。即已访问与未访问。 ↩︎ ↩︎
检查 $u$ 点到该点的距离，如果小于原本该点的距离，则更新为点 $u$ 的距离加上节点之间边的权值 $w$ 。 ↩︎