最短路系列—朴素版Dijkstra算法

朴素版Dijkstra

描述

• 单源最短路，一个定点到另一个顶点的最短路径算法
• 所有边权都是正数
• 适用于稠密图。（边数较多的图 m = n^2 其中， n为顶点，m为边数）
• 稠密图适合邻接矩阵来存储，稀疏图适合用邻接表存储。
• 最短路问题通常只用考虑有向图（无向图可以用有向图来实现）。

算法思路

• 使用数组dist存储源点到其他点的距离。
• 数组s存储当前已经确定的最短距离的点。
• 初始化，dist[0] = 0，其余dist[i] = INT_MAX (一个较大的值即可)
• 循环处理。
  1. 找到不在s中的距离最近的点t
  2. t加入到s中。
  3. 用t更新其他所有点的距离x。 如果dist[x] > dist[t] + g[t][x],则dist[x] = dist[t] + g[t][x]
  4. 重复以上循环。

题目

849 Dijkstra求最短路 I

描述

• n个点m条边有向图，图中可能存在重边和自环，所有边权为正值。
• 求1号点到n号点的最短距离，无法从1到n，输出-1.

输入格式

• 第一行 整数n m。
• 接下来m行，每行x, y,z, 表示存在从x到y的边长为z的有向边。

输出格式

• 输出一个整数，表示从1到n的最短距离。
• 如果路径不存在，输出-1。

数据范围

$1$ $⩽$ n $⩽$ 500
$1$ $⩽$ m $⩽$ 1 0 5 10^5 105
所涉及边长不超过10000.

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

代码

#include #include #include using namespace std;const int N = 510;int n, m;int g[N][N];  //存储输入数据，稠密图，用二维矩阵存储int dist[N];  //存储源点到其他点的最短距离bool st[N]; //每个点的最短路是否确定int dijkstra() {    memset(dist, 0x3f, sizeof dist);    dist[1] = 0; for (int i = 0; i < n; i ++) {     int t = -1;    for (int j = 1; j <= n; j ++) {    if (!st[j] && (t == -1 || dist[j] < dist[t])) // 找到不在st中的距离最近的点j    t = j;    }    st[t] = true;  //t加入到st中    for (int j = 1; j <= n; j ++)    dist[j] = min(dist[j], dist[t] + g[t][j]); //用t更新其他所有点的距离    }    if (dist[n] == 0x3f3f3f3f) return -1; // 说明1到n不连通 return dist[n];}int main() {scanf("%d%d", &n, &m);    memset(g, 0x3f, sizeof g);  //初始化为无穷大while (m --) {int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);  //去除重边和自环的影响} printf("%d\n", dijkstra()); return 0;}

运行结果

acwing评测器已提交AC。另外想自己测试验证重边，自环等问题验证一下。
C++在线工具 测试了几组数据，符合预期。

• 自环边
  输入：
  
  输出：
  
• 重边
  输入：
  
  输出：
  

参考

1. 朴素Dijkstra算法
2. 搜索与图论(二)
3. 关于memset函数和赋值0x3f，2021-5-5