迪杰斯特拉(Dijkstra)算法（C/C++)

迪杰斯特拉（Dijkstra）算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Dijkstra）在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。适用的是单源路径最短路问题，对于多源则采用弗洛伊德（Floyd）算法。

基本思想：

1. 创建一个集合S，用于存储已经找到最短路径的顶点。

2. 将所有顶点的最短路径估计值初始化为无穷大（或一个非常大的数），除了源点其值为0。

3. 不断从未加入S的顶点中选择一个具有最小估计值的顶点u，加入到S中。

4. 更新u的所有邻接顶点v的最短路径估计值。如果通过u到达v的路径比当前已知的路径更短，则更新v的估计值。

5. 重复步骤3和4，直到所有顶点都被加入到S中。

Dijkstra算法的时间复杂度为O(n^2)

下面介绍Dijkstra算法最重要的思想，如果A->B的代价为10，A->C的代价为1，C->B的代价为2，那么我们可以采用绕路的方式，把C点当作中转点，路线为ACB，这样代价为3小于A直接到B的代价10。

图解算法：

下面放一张Dijkstra算法的动态实现图，方便大家理解一下Dijkstra算法的主要思想。没有看懂没有关系，下面我会一步一步的详解。图片来自全栈程序员站长。

下面我们将以此图为例子进行一步一步讲解。

初始：

我们初始设有6个点，起点为a，终点为b，每个点到另一个点的距离如图所示，如果不能到达则为inf，Dis数组为起点到任意一点的最短距离，vis为标记数组，每次寻找最短距离。起点到起点不需要任何代价，所以为0，标记为true。

第一步：

从起点到能够到达的点更新最小距离，与6号点相邻能到达的有1、3、5号点，距离分别为9、2、9，在Dis数组里面都比inf要小，所以更新其值。我们寻找其中最小的距离为2（3号结点），那么我们就更新vis数组标记为true。

第二步：

由3号点可以到达2、4号点，我们发现起点到2号点的距离为2+10=12<inf，所以更新Dis数组，起点到4号点为2+11=13<inf，所以更新Dis数组。此时Dis数组中的最短距离为9，对应5号点。把5号点标记为true。

第三步：

由5号点可以到达4号点，那么由5号点作为中转点，起点到达4号点的距离为9+6=15>13，所以不更新Dis数组，此时Dis数组中最小的为12（2号点），把2号点vis标记为true。

第四步：

由2号点可以到达4号点，2号点作为中转点，起点到达4号点的距离为2+10+15=27<13，所以Dis数组不更新。此时Dis数组中最小值为13（4号结点），标记vis数组。

第五步：

此时没有被标记的点且Dis数组中最小的值为1号点，那么标记1号点，1号点可以到达2、3号点，把1号点作为中转点，起点到达2号点的距离为14+7=21<12，不更新，起点到达2号点的距离为14+9=23<2不更新，此时vis数组都标记完成，算法结束，起点到每个点的最小距离为Dis数组。

视频讲解可以看一下这意味B站up主的，博主觉得他讲的非常好，通俗易懂，-->点击直达<--

C++实现示例：

#include<iostream>
using namespace std;
int n,e,s;//n个顶点，e条边，s是起点
const int inf=0x7fffff;
int dis[101];//dis[i]起点到i的最短距离
int cheak[101];//标记是否找到
int graph[101][101];//记录路径i->j有路径
 
int main(){
  for(int i=1;i<=100;i++){//初始无穷大
    dis[i]=inf;
  }
  cin>>n>>e;
  for(int i=1;i<=e;i++){//邻接矩阵存储
    int a,b,c;
    cin>>a>>b>>c;
    graph[a][b]=c;
  }
  cin>>s;
  dis[s]=0;//起点到起点不需要带价
  for(int i=1;i<=n;i++){
    int minn=inf,minx;
    for(int j=1;j<=n;j++){
      if(dis[j]<minn&&cheak[j]==0){//寻找此点到其他点的最小距离
        minn=dis[j];
        minx=j;
      }
    }
    cheak[minx]=1;//标记到达的最小点
    for(int j=1;j<=n;j++){//更新以最小距离点最为中转点的最小距离
      if(graph[minx][j]>0){
        if(minn+graph[minx][j]<dis[j]){
          dis[j]=minn+graph[minx][j];
        }
      }
    }
  }
  for(int i=1;i<=n;i++){//打印最短距离
    cout<<dis[i]<<" ";
  }
  return 0;
}

算法例题：

Dijkstra算法直接考一般是不会直接考的，都是跟一些其他算法，或者新定义的概念结合起来考，由于Dijkstra算法原理很简单，考察Dijkstra算法更加偏向于其他算法的结合。下面我选取一个例题讲解。

AcWing 4275. Dijkstra序列

Dijkstra 算法是非常著名的贪心算法之一。

它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。

它由计算机科学家 Edsger W. Dijkstra 于 19561956 年构思并在三年后出版。

在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。

在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。

因此，通过 Dijkstra 算法，我们可以逐步生成一个有序的顶点序列，我们称之为 Dijkstra 序列。

对于一个给定的图，可能有多个 Dijkstra 序列。

例如，{5,1,3,4,2} 和 {5,3,1,2,4} 都是给定图的 Dijkstra 序列。

注意，序列中的第一个顶点即为指定的特定源顶点。

你的任务是检查给定的序列是否是 Dijkstra 序列。

输入格式

第一行包含两个整数 N 和 M，表示图中点和边的数量。

点的编号 1∼N。

接下来 M 行，每行包含三个整数 a,b,c，表示点 a 和点 b 之间存在一条无向边，长度为 c。

再一行包含整数 K，表示需要判断的序列个数。

接下来 K 行，每行包含一个 1∼N 的排列，表示一个给定序列。

输出格式

共 K 行，第 i 行输出第 K 个序列的判断，如果序列是 Dijkstra 序列则输出 Yes，否则输出 No。

数据范围

1≤N≤1000,

1≤M≤10^5,

1≤a,b≤N,

1≤c≤100,

1≤K≤100,

保证给定无向图是连通图，

保证无重边和自环（官网没提，但是经实测，官网数据符合此条件）。

输入样例：

5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4

输出样例：

Yes
Yes
Yes
No

解题思路：

此题主要是考察了Dijkstra的逆向解决思路。题意是给定一个序列，让判断是否是Dijkstra序列，当然这个题的新概念Dijkstra序列也是很好理解的，上面我们图解算法，每一步都能标记一个点，这就是本题所说的Dijkstra序列，我们的解题思路就是验证即可，唯一不同的就是每一步选取一个最短距离的点，与给定的序列顺序比较是否为一致。判断一致需要看其他点是否被标记过，并且还有没有比此点距离还小的点。如果给定的序列中有任意一个点不满足，那么它就算不是Dijkstra序列，如果都满足，就是Dijkstra序列。

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=105;
int n,m;
int a[1005];
int g[1005][1005];
bool cheak[1005];
int dis[1005];
bool dij(int x){
  dis[x]=0;//起点到起点初始
  cheak[x]=1;
  for(int i=1;i<=n;i++){//给定序列的n个点进行验证
    int t=a[i];
    cheak[t]=1;//标记此点
    for(int j=1;j<=n;j++){//查看此点是否为最短距离的点
      if(!cheak[j]&&dis[j]<dis[t]){//还有距离更短的点，则不满足
        return false;
      }
    }
    for(int j=1;j<=n;j++){//由此点作为中转点，绕路更新最短距离
      if(dis[t]+g[t][j]<dis[j]&&g[t][j]>0){
        dis[j]=dis[t]+g[t][j];
      }
    }
  }
  return true;
}
int main(){
  cin>>n>>m;
  memset(g,inf,sizeof(g));//初始无穷大，不能到达就是无穷大
  for(int i=1;i<=m;i++){
    int x,y,z;
    cin>>x>>y>>z;
    g[x][y]=g[y][x]=z;//无向边
  }
  cin>>m;
  while(m--){
    memset(cheak,0,sizeof(cheak));//初始化0
    memset(dis,inf,sizeof(dis));
    for(int i=1;i<=n;i++){
      cin>>a[i];
    }
    cout<<(dij(a[1])?"Yes":"No")<<endl;
  }
  return 0;
}

题目不再过多举例，比较难的都是Dijkstra与其他算法的集合，博主将会单独出一篇讲解。下篇更新弗洛伊德（Floyd）算法。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。