本篇文章主要介绍了Dijkstra迪杰斯特拉算法的C++实现，文章包含两个部分，在第一部分中我会简单介绍迪杰斯特拉算法以及一些个人的理解，第二部分会对C++代码的逻辑进行解释。下面是我已经上传的代码资源，大家有兴趣的可以点击链接下载资源。
迪杰斯特拉算法的C++实现

迪杰斯特拉算法本质上是一个贪心算法，通过不断迭代取得局部最优解的方法，最终找到整体的最优解。迪杰斯特拉算法主要用于在有权图中计算出各节点到初始节点的最短路径。在接下来的分析中我会使用的有权图如下 :

其中，ABCDE就是我们需要遍历的节点，连接节点的弦上的数字表示了两节点之间的"距离"，或称之为权重，消耗。需要注意的几点是 :

1. 迪杰斯特拉算法适用的有权图中，节点之间的权重不要求是双向的，即 A-> B的权重和 B->A 的权重不要求相同。换而言之，有权图中节点之间的连接可以是单向的，或者在两个方向权重有所不同的。
2. 迪杰斯特拉算法适用的有权图中，节点间连接的权重值不能是负值。

了解了迪杰斯特拉算法的一些注意点之后，我们下面来重点解释算法的实现。之前我们已经提到了，迪杰斯特拉算法多用于解决最短路径问题，对应上述有权图就是计算出所有节点到初始节点的最短距离。在下述例子中，我们默认使用A作为初始节点,目标就是找出所有节点到A的最短距离以及所经过的路径。
首先我们需要两个列表，一个visited列表用于存放已经遍历过其所有邻节点的节点，一个unvisited列表用于存放还未遍历过其所有邻节点的节点。我们会不断地进行迭代运算，直到unvisited列表为空，即所有的节点都已经访问过(遍历过其所有邻节点)。
显然初始状态，visited列表为空[]，unvisited列表中包含所有的节点[A,B,C,D,E]。
然后我们需要一个列表用于记录所有节点到A节点，起始节点之间的最短距离，以及最短路径中该节点之前的节点。
第一步，初始化这个表格 :
显然A到A的距离为0，其余节点到A的距离为未知，初始化为正无穷。

那么每一次迭代，我们需要做的，就是在unvisited列表中，选择一个到A距离最短的节点，并遍历更新其所有unvisited列表中的邻节点。
例如第一次迭代中，unvisited未访问列表中A节点到A的最短距离最短，那么我们首先就访问A所有unvisited的节点 B 和 D。简单来说，如果通过A访问B比起之前的方式要距离更短，那么我们就更新B到初始点的距离为新的最短距离，并将B之前的节点更新为A。那么在这个例子中，通过A访问B的距离为6，通过A访问D的距离为1，显然距离都比正无穷要小，则更新列表如下 :

同时更新visited列表以及unvisited列表:
visited : [A]
unvisited : [B,C,D,E]

既然未访问列表仍然不为空，我们继续迭代，选择D作为新的访问节点，因为节点D目前到A的距离最短。那么节点D在unvisited列表中的邻节点有 B E，那么我们更新B，E的值和其原来的距离进行对比。 B : 1+2 = 3 < 6   \space   E : 1+1 = 2 < $\infty$。
更新列表如下 :

同时更新visited列表以及unvisited列表:
visited : [A,D]
unvisited : [B,C,E]
我们继续迭代,方法同上。
访问E节点，更新列表 :

同时更新visited列表以及unvisited列表:
visited : [A,D,E]
unvisited : [B,C]

继续访问B，更新列表 :
B的唯一没有访问的邻节点为C，但A> … >B>C 的距离为 3+5=8 >7，因此C到节点A的距离不变。

同时更新visited列表以及unvisited列表:
visited : [A,D,E,B]
unvisited : [C]
最后我们访问C，列表不变，因为C的所有邻节点都已经访问过了。
最终的结果如下 :

通过迪杰斯特拉算法，我们可以完备地遍历所有有权图中的节点，并在最后返回一个所有节点到初始点的最短距离，以及对应的最短路径的所有节点之前的节点。之后通过不断访问最短路径中该节点之前的节点，我们就可以很简单地还原出最短路径。例如对节点C而言，C之前的节点为E，E之前的节点为D，D之前的节点为A，因此最短路径还原为A > D > E > C。

参考 :
[1] Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm

[2] (熟肉)Dijkstra算法详解，轻松入门——Youtube

迪杰斯特拉算法，用于解决单源最短路径问题。

伪代码

//G为图，一般设成全局变量；数组d为源点到达各点的最短路径长度，s为起点
Dijstra(G, d[], s){
    初始化;
    for(循环n次){
        u = 使d[u]最小的还未被访问的顶点的标号;
        记u已被访问;
        for(从u出发能到达的所有顶点v){
            if(v未被访问 && 以u为中介点使s到顶点v的最短距离d[v]最优){
                优化d[v];
                //如果要记录路径，则
                另v的前驱为u;
            }
        }
    }
}

预定义

const int MAXV = 1000; //最大顶点数
const int INF = 1000000000; //设INF为一个很大的数

邻接矩阵版

//邻接矩阵版
int n, G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数

int d[MAXV]; //起点到达各点的最短路径长度
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初值均为false

void Dijkstra(int s){ //s为起点
    fill(d, d+MAXV, INF); //fill函数将整个d数组赋为INF（慎用memset）
    d[s] = 0; //起点s到达自身的距离为0

    for(int i=0; i<n; i++){ //循环n次
        int u=-1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
        for(int j=0; j<n; j++){ //找到未访问的顶点中d[]最小的
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        //找不到小于INF的d[u]，说明剩下的顶点和起点s不流通
        if(u == -1) return;
        vis[u] = true; //标记u为已访问

        for(int v=0; v<n; v++){
            //如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
            if(vis[v] == false && G[u][v] != INF && d[u]+G[u][v] < d[v]){
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

邻接表版

//邻接表版
struct Node{
    int v, dis; //v为边的目标顶点，dis为边权
};
vector<Node> Adj[MAXV]; //图G，Adj[u]存放从顶点u出发可以到达的所有顶点
int n; //n为顶点数，图G使用邻接表实现，MAXV为最大顶点数
int d[MAXV]; //起点到达各店的最短路径长度
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初值均为false

void Dijkstra(int s){ //s为起点
    fill(d, d+MAXV, INF); //fill函数将整个d数组赋为INF（慎用memset）
    d[s] = 0; //起点s到达自身的距离为0

    for(int i=0; i<n; i++){ //循环n次
        int u=-1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
        for(int j=0; j<n; j++){
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
    }
    //找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
    if(u == -1) return;
    vis[u] = true; //标记u为已访问

    //只有下面这个for与邻接矩阵的写法不同
    for(int j=0; j<Adj[u].size(); j++){
        int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
        if(vis[v] == false && d[u] + Adj[u][j].dis < d[v]){
            //如果v未访问 && 以u为中介点可以使d[v]更优
            d[v] = d[u] + Adj[u][j].dis; //优化d[v]
        }
    }
}

如果需要记录一条完整的路径，那么可以在更新d[v]的时候记录前驱。

DFS函数用来递归求路径。

邻接矩阵版：

//还可以利用pre[]数组，表示从起点s到顶点v的最短路径上v的前一个顶点（即前驱结点）的编号
//邻接矩阵版
int n, G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数

int d[MAXV]; //起点到达各点的最短路径长度
int pre[MAXV]; //pre[v]表示从起点到顶点v的最短路径上v的前一个顶点（新添加）
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初值均为false

void Dijkstra(int s){ //s为起点
    fill(d, d+MAXV, INF); //fill函数将整个d数组赋为INF（慎用memset）
    for(int i=0; i<n; i++) pre[i] = i; //初始状态设每个点的前驱为自身（新添加）
    d[s] = 0; //起点s到达自身的距离为0

    for(int i=0; i<n; i++){ //循环n次
        int u=-1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
        for(int j=0; j<n; j++){ //找到未访问的顶点中d[]最小的
            if(vis[j] == false && d[j] < MIN){
                u = j;
                MIN = d[j];
            }
        }
        //找不到小于INF的d[u]，说明剩下的顶点和起点s不流通
        if(u == -1) return;
        vis[u] = true; //标记u为已访问

        for(int v=0; v<n; v++){
            //如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
            if(vis[v] == false && G[u][v] != INF && d[u]+G[u][v] < d[v]){
                d[v] = d[u] + G[u][v];
                pre[v] = u; //记录v的前驱顶点是u（新添加）
            }
        }
    }
}

//求路径
void DFS(int s, int v){ //s为起点编号，v为当前访问的顶点编号（从终点开始递归）
    if(v == s){ //如果当前已经到达起点s，则输出起点并返回
        printf("%d\n",s);
        return;
    }
    DFS(s, pre[v]); //递归访问v的前驱结点pre[v]
    printf("%d\n",v); //从最深处return回来之后，输出每一层的顶点号
}

如果碰到有两条及以上可以达到最短距离的路径，题目可能给出一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径。而第二标尺常见的是以下三种出题方法或其组合：

1. 每条边再增加一个边权（比如花费），要求多条路径取花费最小（边权也可以是其他含义，要求其边权和最大）
2. 每个点增加一个点权（比如收集到的物资），要求多条路径取点权之和最大（如果点权是其他含义的话也可以是最小）
3. 直接问有多少条最短路径

解题方法：只需要增加一个数组来存放新增的边权 或 点权 或 最短路径条数，然后在Dijkstra算法中修改优化d[v]的那个步骤即可。

详细解法：

1. 新增边权。以新增的边权代表花费为例。
   • cost[u][v]表示u->v的花费（由题目输入）
   • 增加数组c[]，表示从起点s到达顶点u的最小花费为c[u]。初始化时c[s]=0，其余c[u]=INF
   • 在d[u]+G[u][v]<d[v]时更新d[v]和c[v]，而当d[u]+G[u][v]==d[v]且c[u]+cost[u][v]<c[v]时更新c[v]

for(int v=0; v<n; v++){
    //如果v未访问 && u能到达v
    if(vis[v] == false && G[u][v] != INF){ //以u为中介点可以使d[v]最优
        if(d[u] + G[u][v] < d[v]){
            d[v] = d[u] + G[u][v];
            c[v] = c[u] + cost[u][v];
        }else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]){
            c[v] = c[u] + cost[u][v]; //最短距离相同时看能否使c[v]最优
        }
    }
}

2. 新增点权。以新增的点权代表城市能收集到的物资为例。
   • weight[u]表示城市u中的物资数目（由题目输入）
   • 增加数组w[]，表示从起点s到达顶点u可以收集到的最大物资为w[u]。初始化时w[s]为weight[s]，其余w[u]=0
   • 在d[u]+G[u][v]<d[v]时更新d[v]和c[v]，而当d[u]+G[u][v]==d[v]且w[u]+weight[v]>w[v]时更新w[v]

for(int v=0; v<n; v++){
    //如果v未访问 && u能到达v
    if(vis[v] == false && G[u][v] != INF){
        if(d[u] + G[u][v] < d[v]){ //以u为中介点可以使d[v]更优
            d[v] = d[u] + G[u][v];
            w[v] = w[u] + weight[v];
        }else if(d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v]){
            w[v] = w[u] + weight[v]; //最短路径相同时看能否使w[v]更优
        }
    }
}

3. 求最短路径条数。
   • 增加数组num[]，表示从起点s到达u的最短路径条数为num[u]，初始化时num[s]=1，其余num[u]=0
   • 在d[u]+G[u][v]<d[v]时更新d[v]，并让num[v]继承num[u]，而当d[u]+G[u][v]==d[v]时将num[u]加到num[v]上

for(int v=0; v<n; v++){
    //如果v未访问 && u能到达v
    if(vis[v] == false && G[u][v] != INF){
        if(d[u] + G[u][v] < d[v]){ //以u为中介点可以使d[v]更优
            d[v] = d[u] + G[u][v];
            num[v] = num[u];
        }else if(d[u] + G[u][v] == d[v]){
            num[v] += num[u]; //最短距离相同时同时累加num
        }
    }
}

参考文献

1. 《算法笔记》

一.基本概念

迪杰斯特拉算法是一种计算图论单源路径最短的算法，算法核心思想是贪心，即保证每一个【被保存的路径】都是通过【前一个路径】得出的，每条路径都是最短的，得出的路径必然是最短的，详细原理证明可以去CSDN社区自行搜索，本文章主要是对迪杰斯特拉算法的一个基本解释和算法实现。

普里姆算法和迪杰斯特拉的算法的差别在哪里呢。笔者认为：

两者都是求“权值”最小，但他们所处的环境不一样，首先谈谈他们的应用场景，迪杰斯特拉能用于有向图，但普里姆算法只能应用于无向图，如果用了有向图，我们不能保证【权值最小】的边来源于我们所选择的边，也就是说：普里姆算法更注重于一条路从头走到尾的消耗，中间的路径怎么样，都无所谓，因为我们选择的边必须全部走完，而迪杰斯特拉算法注重于，每条单元路径都是最短最优的，使得整棵树都是最优的

所以迪杰斯特拉一般用于解决单源最短路径问题。

二.算法思想

迪杰斯特拉的思想在于决策层的建立（这个并不是名词，是笔者为了便于理解所提出的），只有一层决策层，这一层包含了所有顶点，每进行一次【顶点选择】都要更新一次【决策层】

算法的核心部分有一个是：当我们找到了当前层的一个最短路径，那么我们就将这个最短路径所对应顶点加入，然后后续决策的时候，该顶点的决策层值不变，有人就要问了？为啥这层找到了，后面就不找了，不能走其他顶点然后再绕回来这个顶点吗，也许权值更小呢？

这就体现出迪杰斯特拉和普里姆算法的区别了，笔者在普里姆算法实现中就提到普里姆的决策层的“由谁决策出来的”是可以变化的，但这里是不可以变化的，为什么？因为权值大于0，其他顶点必定大于这个“最短路径顶点权值”,你现在都已经比这个权值大了，后续无论怎么加都会比当前这个决策要更大的，所以我们每次找到一个最短路径，马上废弃掉，进行保存

我们找到一条最短路的操作可以执行很多次，不断的找边，定边，直到所有边都被定好是最短路径了，那么迪杰斯特拉算法也就结束了。

迪杰斯特拉在数据结构中一直为大学学生所害怕，毕竟图论的算法确确实实都很抽象也都挺麻烦的

那么本篇文章将从代码实现方面一步一步指导读者手写出迪杰斯特拉算法。

三.代码实现

（1.）操作步骤

要实现一个算法，我们不止要写完这次就结束了，我们更应该尝试的去理解他的底层原理（迪杰斯特拉算法的原理证明确实是非常难以理解的，所以我们只需要按部就班，学会了怎么写就行了，因为贪心算法很多时候都是突发奇想，需要严谨的数学证明，但如果举不出反例，那就是对的），然后分析他的代码实现步骤，和伪代码变成真正的代码。

实现步骤如下：

1.将起点的边权关系加入【决策层】数组

2.选择【决策层数组】中权值最小的一条边的另一端称【新节点】，然后看看新节点的加入是否能使得原来【不能走通的路】和【走的路权值比现在费劲】的路变最优，更新完以后，将被更新的点设置成当前的【主动更新这个点的点】作为他的最后的路径，由于这个【新节点】已经找到了最短路径，那么标记为【不可访问】

3.循环（2.）的决策，直到所有的边都被决策了（解释：由于每次我们都至少选择一条最短的边，所以我们一定会选择【图的边数】次，这里直接进行for循环，不必担心选不到）

4.结束，输出。

（2.）伪代码

这里实际实现笔者先不给出，我们先分析我们需要什么，根据我们的操作步骤，我们需要

1.决策层数组 int Distance[] //也叫最短路径数组，记录了每个点的最短路径

2.标记数组 bool Done //如果某个顶点已经找到了路径了，我们需要标记，防止重复选择

3.路径数组 int path[]//路径数组，只需要保存某个数组被找到最短路径前【是谁更新的他】的顶点即可，为什么只需要保存最后一次的呢，因为前一个顶点也是由前前一个顶点的最优路径走出来的，换言之，你只需要最后一个前顶点，顺着他逆推就可以找到全部的路径了！

4.邻接矩阵 edge[][]//这里由于对边的请求较多，直接使用邻接矩阵，方便查询

代码的步骤

1.初始化邻接矩阵 //初始化操作笔者不作多讲，既然有兴趣实现不可能初始化不出来

2.加入起点中的边权到决策层数组

3.循环决策

故，伪代码可以写成

void ShortestPath(Graph& g)
{
   决策层数组
   路径数组
    访问数组
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            初始化决策层
        }
    }
    访问数组[起点]=true//起点已经被访问了
    Distance[起点]=0//起点到自己的点是0
    path[起点]=-1//用于后面输出时候的标记，遇到-1停止输出路径
    for(int i=0;i<n;i++)
    {
        for(xxx)找权值最小的边
        Done[],path[],mineid//标记一下已经被访问了，标记一下路径，标记一下他的下标，后面更新用
        for(xxx)更新决策层
    }
    Show();//输出矩阵

}

(FINALL)真代码实现

我们写好了伪代码以后，一个一个对着实现

class Graph
{
public:
    int vernum;
    int edgenum;
    int edge[10][10];
    string ver[10];
    void init();
    int Locate(string s);
};

int Graph::Locate(string s)
{
    for (int i = 0;i < vernum;i++)
    {
        if (ver[i] == s)return i;
    }
    return -1;
}
void Graph::init()
{
    cout << "请输入：顶点个数 边数" << endl;
    cin >> this->vernum >> this->edgenum;
    cout << "初始化完成，请输入顶点信息" << endl;
    for (int i = 0;i < this->vernum;i++)
    {
        cin >> this->ver[i];
    }
    cout << "初始化完毕，下面开始初始化边" << endl;
    cout << "=============================" << endl;
    
    for (int i = 0;i < vernum;i++)
    {
        for (int j = 0;j < vernum;j++)
        {
            if (i == j)edge[i][j] = 0;
            else
            {
                edge[i][j] = INT_MAX;
            }
        }
    }
    for (int i = 0;i < edgenum;i++)
    {
        string start, end;
        cin >> start >> end ;
        int s = Locate(start);
        int e = Locate(end);
        cin >> edge[s][e];
    }
    return;
}
#include <stack>;
void Show(int distance[], int path[],Graph& g,int start)
{
    for (int i = 0;i < g.vernum;i++)
    {   
        if (i != start&&distance[i]<INT_MAX)
        {
            cout << g.ver[start] << "到达" << g.ver[i] << "最短路径为" << distance[i]<<" 路径：";
            stack<int>s;
            int pre = path[i];
            s.push(i);
            while (pre != -1)
            {
                s.push(pre);
                pre = path[pre];
            }
            while (!s.empty())
            {
                cout << g.ver[s.top()];
                if (s.size() > 1)cout << "-->";
                s.pop();
            }
            
            cout << endl;
        }
        else if (distance[i] = INT_MAX)
        {
            cout << g.ver[start] << "无法到达" << g.ver[i] << "! "<<endl;
        }
    }
    return;
}

void Dijkstra(string point, Graph g)
{  
    cout << "迪杰斯特拉的算法如下：" << endl;
    int start = g.Locate(point);
    bool Done[100];
    int Distance[100];
    int path[100];
    for (int i = 0;i < g.vernum;i++)
    {
        Done[i] = false;
        Distance[i] = g.edge[start][i];
        if (Distance[i] < INT_MAX)
        {
            path[i] = start;

        }
        else
        {
            path[i] = -1;
        }
    }
    Done[start] = true;
    Distance[start] = 0;
    path[start] = -1;
    for (int i = 0;i < g.vernum;i++)//找最值，更新最值带来的影响
    {
        int minval = INT_MAX, u = start;
        for (int j = 0;j < g.vernum;j++)
        {
            if (!Done[j] && Distance[j] < minval)
            {
                minval = Distance[j];
                u = j;//找最值
            }
        }
        Done[u] = true;
        for (int k = 0;k < g.vernum;k++)
        {
            if (!Done[k] && g.edge[u][k] < INT_MAX && Distance[u] + g.edge[u][k] < Distance[k])//找影响
            {
                Distance[k] = Distance[u] + g.edge[u][k];
                path[k] = u;
            }
        }
    }
    Show(Distance, path,g,start);
}

（代码很长，请耐心观看）

这里有个小BUG需要提醒一下，因为书上可能没有注意到

就是更新路径的时候经常判断 某一点的权>当前点的到这点的路径权值+当前点的最短路径

来看看是不是能更新，但如果后者是INT_MAX最大值，如果权值很大的情况下

极有可能溢出

可以将等式换成 某一点的权减去当前点到这点的路径权是否大于当前点的当前路径

这个等式在弗洛伊德算法中笔者会提到

输出矩阵写一个Show函数，使用栈进行递归操作即可

成果展示

 参照了B站王卓老师的测试样例，结果一致

再谈迪杰斯特拉算法：

迪杰斯特拉算法对大众考研学子和数据结构及算法爱好者都是入门的一个算法，如果读者害怕自己学不会学不好，无法理解，那就多看几遍，笔者也是从只会写链表到手写迪杰斯特拉算法的，没有谁学数据结构是一路通窍的，笔者学KMP曾半个月走不出next数组的坑里，最后也大彻大悟了

另外笔者分享一下在写算法类题目时的感想：

其实迪杰斯特拉算法和DFS,BFS的本质差不多，都是通过“搜索”来完成对某路径的查找，但其实DFS,BFS一样也能通过设定回溯数组或者其他操作来找到最短路，但显然DFS,BFS是暴力搜索，每一步的探索都是没有目的的盲目搜索，和迪杰斯特拉的贪心搜索效率差很多，但笔者认为：当任意一个顶点，他都能向上下左右走通，并且边权为0,1的时候，迪杰斯特拉其实跟DFS,BFS差不多，因为迪杰斯特拉需要通过边权关系来模拟贪心来达到最快最优解，而此时边权意义不大的时候，迪杰斯特拉也就失去了他的优势，但很显然我们大部分的应用还是有边权的，读者可以根据自己的题目情况，来确认使用深广搜还是迪杰斯特拉，不过目前算法题（LEETCODE为主）中很少见直接使用迪杰斯特拉算法的

最后感谢您的阅读。

文章为笔者笔记，如果文章有错误之处，描述不当之处还请您告知。

希望这篇文章能给您带来一些收获