文章目录
前言
一、Dijkstra是什么？
二、例题，代码
1.AcWing 849. Dijkstra求最短路 I
本题分析
AC代码
2.AcWing 850. Dijkstra求最短路 II
本题分析
AC代码
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Dijkstra。
一、Dijkstra是什么？
Dijkstra的思路：通过n次遍历，每次找到没有确定最短距离的点，并拿这个点去更新其他未更新的点，堆优化版Dijkstra用到了堆，关于堆（优先队列STL）的用法见：STL—priority_queue，手写堆见这篇博客：数组模拟堆，下图是求最短路的不同情况对应的不同算法，图片来自：AcWing算法基础课
二、例题，代码
1.AcWing 849. Dijkstra求最短路 I
本题链接：AcWing 849. Dijkstra求最短路 I
本博客给出本题截图：
本题分析
int g[N][N];g数组存的是两点之间的距离，例如g[i][j]存的是从i号点到j号点的距离
int dist[N];dist数组存的是到起点的距离，例如dist[i]存的是i号点到1号点的距离
一开始，我们需要对以上两个数组初始化为正无穷即0x3f3f3f3f，距离为正无穷意味着还没有遍历到这个点，bool st[N]存的是是否被遍历，例如st[i]表示的是i号点的距离是否已经被更新，如果st[i] == true;意味着被更新，否则代表着没有被更新，st数组的初始都为false，代表没有一个点被遍历到，Dijkstra更新距离的核心是：
for (int i = 0; i < n; i ++ ) //n次循环，确定n个点的最短路径 { int t = -1; //表示还没有更新点 for (int j = 1; j <= n; j ++ ) if ((t == -1 || dist[t] > dist[j]) && !st[j]) //寻找还未确定最短路径的点中路径最短的点 t = j; //找到的点赋值给t，此时的t就是还未确定最短路径的点中路径最短的点 st[t] = true; //表示这个点被找到了，下次更新的时候跳过这个点 //然后用这个点更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min (dist[j], dist[t] + g[t][j]); //j号点到起点距离的值为从t点到起点的距离 + t到j的距离和j到起点距离的最小值 }
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510; int g[N][N]; int dist[N], n, m; 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 ((t == -1 || dist[t] > dist[j]) && !st[j]) t = j; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min (dist[j], dist[t] + g[t][j]); } if (dist[n] == 0x3f3f3f3f) return -1; else return dist[n]; } int main() { cin >> n >> m; memset(g, 0x3f, sizeof g); while (m -- ) { int x, y, c; cin >> x >> y >> c; g[x][y] = min(g[x][y], c); } int t = dijkstra(); cout << t; return 0; }
2.AcWing 850. Dijkstra求最短路 II
本题链接：AcWing 850. Dijkstra求最短路 II
本博客给出本题截图：
本题分析
稀疏图用到了链表的存储方式，单链表的详细做法见：链表
因为我们求的是最短路，所以在堆优化版本中我们用到了小根堆，小根堆的用法详见：STL—priority_queue，小根堆中我们需要存储一个pair，存储距离和点，在进行排序的时候注意是按照距离排序，所以我们必须把距离存储到first中
AC代码
#include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cstdio> using namespace std; typedef pair<int, int> PII; const int N = 1e6 + 10; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } cout << dijkstra() << endl; return 0; }
