适用情景

在最短路问题当中的单源最短路(一号点到其他所有点之间的距离)的只有正权边的情况。

时间复杂度

O(N^2)

算法解释（朴素版的Dijkstra）

首先是关于这个图的存储，图的话主要是分为稠密图与稀疏图。稠密图就是说n的平方与m是一个量级的，对于稠密图的话，用邻接矩阵来存；稀疏图的话是n与m为一个量级的，对与稀疏图的话，就用邻接表来存。在这边我先举一个用邻接矩阵存图为例子吧。

int g[N][N];

然后这个邻接矩阵等会儿我是要把具体的边的信息放进去的，所以在一开始有必要进行一些预处理初始化，在最短路问题当中有两类特殊情况：这就是重边，一个就是自环，由于当下背景是最短路，对于重边而言的话，只需要取小的就可以；然后对于自环而言的话，不能是负环（不然最短路就变成负无穷了），然后对于正环而言的话，在最短路里相当于没有，所以就这样初始化

for (int i=1;i<=n;i++)
{for (int j=1;j<=n;j++){if (i==j){g[i][j]=0;}else{g[i][j]=0x3f3f3f3f;  //为等会儿输入边权重取小做准备}}
}

然后还需要开两个数组，一个数组就是用来记录一下该点是不是已经确定了最短路距离，还有一个数组用来记录一下每点到一号点之间的最短路距离是多少，一开始的话每点初始化为正无穷（当然，一号点除外，它到他自己本身的距离就是0

int st[N];
int dist[N];
memset(dist,0x3f3f3f3f,sizeof(dist));
dist[1]=0;

然后往邻接矩阵里面输入每一条边的有关信息.

while(m--)
{int a,b,c;scanf("%d %d %d",&a,&b,&c);g[a][b]=MIN(g[a][b],c);
}

然后就进入了迪杰斯特拉算法的精髓：首先要去找到这么一个点：1. 还没有被正式确认下来最短路距离，2. 到1号点的距离比其他与他一样的同胞（还没有被正式确认最短路距离）到一号点的距离都要短(因此逃不开还要遍历一遍所有点)。先把这个点去找到，这个点找到之后，去遍历一下这个点所能连接到的其他点，看一看能不能更新那些点的最短路距离。遍历一圈完成之后，这个点的最短路距离也就正式被确定下来。然后依次往复，不断循环。显而易见，每一次循环确定下来一个点的最短路距离，既然有n个点，那么就需要n次循环

for (int i=0;i<n;i++)
{int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],dist[t]+g[t][j]);}
}

然后由于迪杰斯特拉算法的要求，就是说所有的边都必须是正权边，因此如果说从一号点走不到n号点的话，那么n号点的距离dist应该还是保持初始化的那个值0x3f3f3f3f，在当前情形是不存在负权边，这个初始化的正无穷大值不会被略微更新小

if (dist[n]==0x3f3f3f3f)
{printf("%d\n",-1);
}
else
{printf("%d\n",dist[n]);
}

例题

来源：AcWing

849. Dijkstra求最短路 I - AcWing题库

#include <stdio.h>
#include <string.h>
#define N 510
#define MIN(a,b) ((a)<(b)?(a):(b))
int g[N][N];
int st[N];
int dist[N];
int main()
{memset(dist,0x3f3f3f3f,sizeof(dist));dist[1]=0;int n,m;scanf("%d %d",&n,&m);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (i==j){g[i][j]=0;}else{g[i][j]=0x3f3f3f3f;  //为等会儿输入边权重取小做准备}}}while(m--){int a,b,c;scanf("%d %d %d",&a,&b,&c);g[a][b]=MIN(g[a][b],c);}for (int i=0;i<n;i++){int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],dist[t]+g[t][j]);}}if (dist[n]==0x3f3f3f3f){printf("%d\n",-1);}else{printf("%d\n",dist[n]);}return 0;
}