版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
Dijkstra算法
单源最短距离算法,可以一次性求出源点u
到其他所有点的最短距离。
算法思路:
- 将所有顶点分为已访问和未访问两类,初始时只有源点
u
是已访问的。 - 从已访问过的结点中找出与源点距离最近的点
t
,再遍历该点的邻接点,如果邻接点未被访问过,则判断能否用t
来更新这个点的最短路径,如果可以,更新邻接点的最短路径和前驱结点。遍历完t的邻接点后,设置t
为已访问状态。 - 以上步骤重复n轮,即可完成全部点的最短距离和前戏结点的更新。
为了实现Dijkstra算法,需要以下额外变量用以记录状态:
dist
数组:dist[i]
表示顶点i
到源点的最短距离,初始时只有源点和与源点直接相邻的点有数值,其他点为无穷大。visited
数组:记录顶点是否被访问过。p
数组:p[i]
表示i
到源点的最短路径上的前一跳,初始时只有源点和与源点直接相邻的点有数值,其他点为-1。
如果只需要求最短路径距离的值,不需要关注到底是哪一条路径,则可以省略p
数组。
Dijkstra算法本质是贪心算法,每一步都是当前状态的最优解。
以下是朴素版本的Dijkstra算法实现:
代码块 |
---|
#define MAXN 1005
#define INF 0x3f3f3f3f
int G[MAXN][MAXN]; // 邻接矩阵,G[u][v]表示顶点u到顶点v的距离,或者为INF,表示u、v之间不存在边
int n; // 顶点数
int dist[MAXN]; // dist[i]表示顶点i到源点的最短距离,初始时只有源点和与源点直接相邻的点有数值,其他点为INF
int p[MAXN]; // p[i]表示i到源点的最短路径上的前一跳,初始时只有源点和与源点直接相邻的点有数值,其他点为-1
int visited[MAXN]; // 表示顶点i是否已访问过
void dijkstra(int u) { // 计算源点u到其他各点的最短距离
// 初始化
for(int i = 0; i < n; i++) {
visited[i] = false;
dist[i] = G[u][i]; // 初始化源点到其他各顶点的距离,可能为INF
p[i] = (dist[i] == INF ? -1 : u); // 与源点相邻,设置前戏结点为u,不相邻,设置前驱结点为-1
}
// 从源点u开始
dist[u] = 0;
visited[u] = true;
// 对所有顶点进行松弛操作
for(int i = 0; i < n; i++) {
// 找出剩余顶点中离源点最近的点
int tmp = INF, t = u;
for(int j = 0; j < n; j++) {
if(!visited[j] && dist[j] < tmp) {
t = j;
tmp = dist[j];
}
}
if(t == u) return;
visited[t] = true;
for(int j = 0; j < n; j++) { // 更新t的邻接点的最短路径长度,松弛操作
if(G[t][j] != INF && !visited[j] && dist[j] > dist[t] + G[t][j]) {
dist[j] = dist[t] + G[t][j];
p[j] = t;
}
}
}
} |
目录 |
---|