Dijkstra适用于稠密图,因此选用邻接矩阵存储数据。
Dijkstra是基于贪心思想的算法,算法过程:
首先,确定一个起始点,将各顶点到起始点的距离初始化为无穷大。然后再将与初始点相邻的其余点依次进行对比,选择距离初始点最近的一个点作为中转点(第一次选取的点为起始点自身,之后将会选取其余点作为中转点)。
然后,以该中转点再来探索与其相邻的点j 的距离,当起始点到点j 的距离小于起始点通过中转点再到点j 的距离,则将后者作为优选路径,完成全部邻接点的更新。
以此类推,依次逐步向目标点延伸,找到最短路径。
具体图示过程可参考:AcWing 849. Dijkstra求最短路 I:图解 详细代码
在表示无穷大时使用0x3f3f3f3f,在表示无穷小时使用0xc0c0c0c0
参考文章:
使用0x3f3f3f3f表示无穷大
含注释代码
#include <stdio.h>
const int N = 510, INF = 0x3f3f3f3f; // INF:无穷大
int n, m;
int g[N][N], dist[N]; // 邻接矩阵g和最短距离数组dist
//int pre[N]; // 构建前驱数组,记录最短路径序列中各节点的直接前驱
bool visit[N]; // 访问记录数组visit
int dijkstra(){
for(int i = 0; i <= n; i++) dist[i] = INF; // 初始化为无穷大
dist[1] = 0; // 编号为1的结点到自身的距离
for(int i = 0; i < n; i++){ // 每遍历一次向前走一步,一共n个点遍历n次
int t = 0; // 存储访问点
for(int j = 1; j <= n; j++){ // 选取中转点
if(!visit[j] && dist[j] < dist[t]) t = j; // 每次选取距离原点最近的点作为中转点
}
visit[t] = true; // 标记已被访问过
for(int j = 1; j <= n; j++){ // 更新原点0至各点的距离
if(dist[t] + g[t][j] < dist[j]){ // 判断经过之前的路径近还是经过中间点t近
dist[j] = dist[t] + g[t][j];
//pre[j] = t; // 记录到达结点j的上一个结点为t
}
}
}
// if(dist[n] == INF) // 若到n为无穷大,说明不存在由结点1到n的路径
// return -1;
// else
// return dist[n]; // 返回最短路径
return dist[n] == INF ? -1 : dist[n];
}
int main(){
scanf("%d%d", &n ,&m);
for(int i = 0; i <=n; i++) // 初始化邻接矩阵g为无穷大
for(int j = 0; j <= n; j++)
if(i != j) g[i][j] = INF;
while(m--){
int x, y, z; scanf("%d%d%d", &x, &y ,&z);
if(g[x][y] > z) g[x][y] = z; // 选取权重最小的边
}
printf("%d", dijkstra());
// 输出最短路径
//puts("");
//for(int i = n; i != 0; i = pre[i]) printf("%d ", i);
return 0;
}
无注释代码
#include <stdio.h>
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool visit[N];
int dijkstra(){
for(int i = 0; i <= n; i++) dist[i] = INF;
dist[1] = 0;
for(int i = 0; i < n; i++){
int t = 0;
for(int j = 1; j <= n; j++){
if(!visit[j] && dist[j] < dist[t]) t = j;
}
visit[t] = true;
for(int j = 1; j <= n; j++){
if(dist[t] + g[t][j] < dist[j]) dist[j] = dist[t] + g[t][j];
}
}
return dist[n] == INF ? -1 : dist[n];
}
int main(){
scanf("%d%d", &n, &m);
for(int i =0; i <= n; i++)
for(int j = 0; j <= n; j++)
if(i != j) g[i][j] = INF;
while(m--){
int x, y, z; scanf("%d%d%d", &x, &y, &z);
if(g[x][y] > z) g[x][y] = z;
}
printf("%d", dijkstra());
return 0;
}