算法简介
迪杰斯特拉算法，是一种基于贪心思想的、用于求解单源最短路径的算法。也就是说，给定一张（不含负权的）图以及一个源点，迪杰斯特拉算法可以很方便地求出各个结点到源点的最短路径。
实例分析
我们从一个具体的例子来看看迪杰斯特拉算法的运行过程。注意，我们
- 用数组dis来记录每一个结点到源点的最短距离；
- 用数组visit来标记结点是否访问过；
- 用数组pre来记录每一个结点的前驱结点，以便求出最短路径。
我们假设源点为①号结点。初始情况下，给dis[1]赋值0，其余均为∞；全部结点均为未访问，visit[]全零。
接下来，我们选取源点①（它正好也是当前与源点距离最小的结点），将其标记为已访问，进行松弛操作。经过松弛操作后，结果变为
具体来说，以松弛结点①到结点②的边为例，我们可以发现原来的dis[2]=∞，新的距离dis[1]+G[1][2]<dis[2]，于是将dis[2]更新为dis[1]+G[1][2]的值1，同时更新前驱结点pre[1]为①号结点。以此类推，可以更新③、④和⑤号结点的情况。
接下来进行第二次贪心选择：在未访问过的结点中，选取与源点距离最近的结点，固定其dis值并标记为已访问。这里②、④均可，不妨选择②号结点：
同样地，以②号结点对与它邻接的边进行松弛。事实上，只有⑤与之邻接（只考虑未访问过的结点，下同），得到
接下来进行第三次贪心选择——选取④：
以④号结点对与它邻接的边进行松弛。事实上，也只有⑥与之邻接，得到
接下来进行第四次贪心选择——选取③：
以③号结点对与它邻接的边进行松弛。事实上，只有⑤号结点与之邻接，但是此处新值dis[3]+G[3][5]>dis[5]，于是无需进行优化松弛。
接下来进行第五次贪心选择——选取⑤：
同样地，以⑤号结点对与它邻接的边进行松弛，也即⑤⑥：
进行最后一次贪心选择——此时只剩下一个结点未访问了，选取它之后，算法运行结束。
代码解析
下面我们来看看如何编写迪杰斯特拉算法。我们先从最基本的算法考虑起。首先，根据上面的实例分析，我们知道需要维护一个邻接矩阵（邻接表当然也可）以及dis、visit和pre数组：
const int N = 1000; // 以1000个结点为例
int G[N][N];
int dis[N];
int visit[N];
int pre[N];接下来进行初始化：
// G, visit, pre均为全局变量时，默认值就是0无需额外的初始化
const int INF = 1000000000;
fill(dis, dis+N, INF);基于贪心思想，迪杰斯特拉算法的伪代码如下。
初始化；
for i from 1 to N:
1.选取未标记过的所有结点中，与源点距离最近的点idx，同时记下该距离minimum
dis[idx] = minimum, visit[idx] = 1;
2.松弛全部与idx结点邻接的、未访问过的边接下来实现上面的1、2两部分代码，就完成了迪杰斯特拉算法的基本实现了。
选取最小dis值
这部分很简单，遍历选取最小值即可。
int minimum = INF, idx = -1;
int j;
for(j=1; j<=N; j++) {
if(visit[j] == 0 && dis[j] < minimum) {
minimum = dis[j];
idx = j;
}
}
if(idx == -1) return; // 如果idx仍等于-1，表示图不连通松弛
松弛操作也即遍历每一条与idx邻接的边，更新最小值即可。
for(j=1; j<=N; j++) {
if(visit[j] == 0 && G[idx][j]) {
// visit[j] == 0表示未访问；G[idx][j]表示不为零即idx和j之间存在边
if(dis[idx] + G[idx][j] < dis[j]) {
// 可以进行松弛操作
dis[j] = dis[idx] + G[idx][j];
}
}
}完整代码
const int N = 1000; // 以1000个结点为例
const int INF = 1000000000;
int G[N][N]; // 邻接矩阵
int dis[N]; // 记录最短距离
int visit[N]; // 记录是否访问过
int pre[N]; // 记录前驱结点索引
void Dijstra() {
// 初始化
fill(dis, dis+N, INF);
// 贪心，选取最小dis值
int minimum = INF, idx = -1;
int j;
for(j=1; j<=N; j++) {
if(visit[j] == 0 && dis[j] < minimum) {
minimum = dis[j];
idx = j;
}
}
if(idx == -1) return; // 如果idx仍等于-1，表示图不连通
dis[idx] = minimum, visit[idx] = 1;
for(j=1; j<=N; j++) {
if(visit[j] == 0 && G[idx][j]) {
// visit[j] == 0表示未访问；G[idx][j]表示不为零即idx和j之间存在边
if(dis[idx] + G[idx][j] < dis[j]) {
// 可以进行松弛操作
dis[j] = dis[idx] + G[idx][j];
}
}
}
}例题
PAT1087
传送门：https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805379664297984?type=7&page=0
