| path | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 2 | 3 | ∞ | ∞ | ∞ | ∞ |
| 2 | 3 | 0 | ∞ | ∞ | 5 | 4 | ∞ | ∞ |
| 3 | 2 | ∞ | 0 | ∞ | ∞ | 4 | 6 | ∞ |
| 4 | 3 | ∞ | ∞ | 0 | 4 | ∞ | 6 | ∞ |
| 5 | ∞ | 5 | ∞ | 4 | 0 | 2 | 2 | ∞ |
| 6 | ∞ | 4 | 4 | ∞ | 2 | 0 | ∞ | 3 |
| 7 | ∞ | ∞ | 6 | 6 | 2 | ∞ | 0 | 3 |
| 8 | ∞ | ∞ | ∞ | ∞ | ∞ | 3 | 3 | 0 |
| dis | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 估计值 | 0 | 3 | 2 | 3 | ∞ | ∞ | ∞ | ∞ |
path代表地图 例如path[i][j]代表从i到j的距离
dis代表从起点到达i的距离，开始时初始化为最大，代表无穷远即未连同
vis代表当前节点[i]是否访问过
既然是求 1 号顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离 1 号顶点最近是 3 号顶点。
当选择了 3 号顶点后，dis[3]的值就已经从“估计值”变为了“确定值”，即 1 号顶点到 3 号顶点的最短路程就是当前 dis[3]值。因为目前离 1 号顶点最近的是 3 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 3 号顶点的路程进一步缩短了。因为 1 号顶点到其它顶点的路程肯定没有 1 号到 3 号顶点短。
既然选了 3 号顶点，接下来再来看 3 号顶点有哪些出边呢。有 3->6 和 3->7 这两条边。先讨论通过 3->6 这条边是否能够让 1 号顶点到 6 号顶点的路程变短。也就是说比较dis[6]和dis[3]+path[3][6]的大小。其中 dis[3] 表示 1 号顶带你到 3 号顶点的路程。dis[3]+path[3][6]中dis[3]表示 1 号顶点到 3 号顶点的路程，path[3][6]表示 3->6 这条边。所以 dis[3]+path[3][6]就表示从1号顶带你到3号顶点，再通过3->6这条边到达3号顶点的路程
我们发现 dis[6]=∞，dis[3]+path[3][6]=6，dis[6] > dis[3]+path[3][6]，因此dis[6]要更新为10。这个过程有个专业术语叫“松弛”。即 1 号顶点到 3 号顶点的路程即 dis[3] ，通过 3->6 这条边松弛成功。这便是Dijkstra算法的主要思想：通过“边”来松弛 1 号顶点到其余各个顶点的路程。
算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：
- 将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个
vis[ i ]数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果vis[ i ]为 1 则表示这个顶点在集合 P 中，如果vis[ i ]为 0 则表示这个顶点在集合 Q 中。 - 设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把
dis[ i ]设为path[s][ i ]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。 - 在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即
dis[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是dis[u]+path[u][v]。如果这个值比目前已知的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。 - 重复第 3 步，如果集合 Q 为空，算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径。
in
8 13
1 2 3
1 3 2
1 4 3
2 6 4
2 5 5
3 6 4
3 7 6
4 5 4
4 7 6
6 8 3
6 5 2
5 7 2
7 8 3
out
1 to 2 min= 3
1 to 3 min= 2
1 to 4 min= 3
1 to 5 min= 7
1 to 6 min= 6
1 to 7 min= 8
1 to 8 min= 9
#include <iostream>
#include <string.h>
#include <cstdio>
#include <stdlib.h>
#include <limits.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define maxn 1000+100
int path[maxn][maxn], dis[maxn]; // 地图 起点到达i的距离
bool vis[maxn]; // 是否访问过
int n, t; // 地标数 路径数
void init() {
for (int i = 0; i < maxn; ++i) {
for (int j = 0; j < maxn; ++j) {
path[i][j] = INF;
}
path[i][i] = 0;
}
}
void dijkstra(){
// 将1到i的距离初始化
for (int i = 1; i <= n; i++) {
dis[i] = path[1][i];
vis[i] = false;
}
vis[1] = true; // 标记起点为访问过的
dis[1] = 0; // 起点到起点的距离为0
for (int i = 2; i <= n; i++) { // 从2号节点遍历到n号节点
int now = -1, minL = INF;
// 遍历一遍dis数组，寻找到未访问过的到1最短的路径长度
for (int j = 1; j <= n; j++) { // 从1到n
if (!vis[j] && minL > dis[j]) { // 如果没有访问过当前节点，并且当前从1到j的距离小于最大长度
now = j; // 更新最短路径的位置
minL = dis[j]; // 最短距离等于当前
}
}
if (now == -1) break; // 未找到
vis[now] = true; // 将now标记为访问过
// 从1开始寻找到j最短的路径
for (int j = 1; j <= n; j++) {
// 没有访问过 并且当前已走的长度加上走到j节点的长度小于当前dis[j]
if (!vis[j] && (dis[now] + path[now][j]) < dis[j]) {
dis[j] = dis[now] + path[now][j]; // 更新从起点到j的最短路径
}
}
}
}
int main() {
freopen("in.txt", "r", stdin); // 从指定文件输入数据 提交时注释掉
// memset(path, INT_MAX, sizeof(path));
while (scanf("%d %d", &n, &t) != EOF) {
init();
for (int i = 0; i < t; i++) {
int from, to, len;
scanf("%d %d %d", &from, &to, &len);
if (path[from][to] > len)
path[from][to] = path[to][from] = len;
}
dijkstra();
for (int i = 1; i <= n; i++) {
printf("1 to %d min= %d\n", i, dis[i]);
}
}
return 0;
}