1. 最短路算法体系
2. 朴素的Djikstra 算法步骤：
初始化：每个点到起始点的距离为无穷大，起始点到起始点的距离为零找最近点：找到此时距离起始点最近的一个节点，并标记为最小距离已确定的点更新距离：根据找到的最近点更新剩下还未确定最近距离的节点的距离例题：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≤105, 图中涉及边长均不超过10000。
输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 502; int n, m; int g[N][N], d[N]; bool str[N]; int dijkstra() { // 初始化每个原点到起始点的距离为无穷大 memset(d, 0x3f, sizeof(d)); d[1] = 0; // 循环的作用：求每一个节点到起始点的最短距离 for(int i = 1; i <= n; i++) { // 找到还未被确定距离的所有点中离起始点最近的点 int t = -1; for(int j = 1; j <= n; j++) { if(!str[j] && (t == -1 || d[t] > d[j])) t = j; } //把上面找到的点标记为确定距离 str[t] = true; // 用上面找到的点更新所有点到起始点的距离 for(int j = 1; j <= n; j++) { d[j] = min(d[j], d[t] + g[t][j]); } } return d[n]; } int main() { cin >> n >> m; memset(g, 0x3f, sizeof(g)); for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; g[a][b] = min(g[a][b], c); //如果有重边则只保存最短的边 } int t = dijkstra(); cout << t << endl; return 0; }3. 堆优化的Dijkstra 算法步骤：
初始化：每个点到起始点的距离为无穷大，起始点到起始点的距离为零找最近点：利用堆的结构特点找到距离起始点最近的节点更新距离：更新这个点的邻接点的最近距离例题：Dijkstra求最短路 II 给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式 第一行包含整数n和m。 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式 输出一个整数，表示1号点到n号点的最短距离。 如果路径不存在，则输出-1。
数据范围 1≤n,m≤1.5×105, 图中涉及边长均不小于0，且不超过10000。
输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; typedef pair<int, int> PII; const int N = 100010; int n, m; int e[N], ne[N], h[N], w[N], idx, d[N]; bool str[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(d, 0x3f, sizeof(d)); d[1] = 0; //创建一个堆，并把起始点入堆 priority_queue<PII, vector<PII>, greater<PII> > heap; heap.push({0, 1}); //堆不为空，把堆顶（距离起始点最近的节点）取出，用这个点更新他的邻接点 while(heap.size()) { auto t = heap.top(); heap.pop(); int distance = t.first, ver = t.second; if(str[ver]) continue; // 去除因为重边而造成的冗余备份 str[ver] = true; for(int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if(d[j] > distance + w[i]) { d[j] = distance + w[i]; heap.push({d[j], j}); } } } if(d[n] == 0x3f3f3f3f3f) return -1; else return d[n]; } int main() { cin >> n >> m; memset(h, -1, sizeof(h)); for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); } cout << dijkstra() << endl; return 0; }