一 、Dijkstra 只适用于单源最短路中所有边权都是正数的情况
二 、存储方式
1、稠密图用邻接矩阵
2、稀疏图用邻接表
三 、算法实现
-
用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。将dist数组赋值为正无穷,dist[1]=0
-
用一个状态数组 st 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。
-
遍历 dist 数组，找到一个节点 : 没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state[i] 赋值1
-
遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i->j 的距离 更新 dist[j] = min(dist[j] , dist[i] + w[i][j])
-
重复以上步骤一直到个点的state状态为真
code:
1 : 邻接表实现
1 #include<iostream>
2 #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
3 using namespace std;
4 const int N = 101010;
5
6 int e[N], ne[N], h[N], w[N], idx;//邻接表
7
8 int dist[N], st[N]; //dist[i] 1号点到i号点的最短距离 st[i] i号点的最短路距离是否确定
9
10 int n, m, x, y, z;
11
12 void add(int a, int b,int c) {
13 e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
14 }
15 void Dijkstra() {
16 memset(dist, 0x3f, sizeof dist);
17 dist[1] = 0;
18 for (int i = 1; i <= n; i++)
19 {
20 int t = -1;
21
22 for (int j = 1; j <= n; j++)
23 if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
24
25 for (int k = h[t]; k != -1; k = ne[k])
26 {
27 int i = e[k];
28 if (dist[i] > dist[t] + w[k]) dist[i] = dist[t] + w[k];
29 }
30 }
31 }
32 int main()
33 {
34 fast;
35 memset(h, -1, sizeof h);
36
37 cin >> n >> m;
38
39 while (m--) {
40
41 cin >> x >> y >> z;
42
43 add(x, y, z);
44
45 }
46
47 Dijkstra();
48
49 cout << dist[n];
50
51 return 0;
52 }
2 : 邻接矩阵实现
1 #include<iostream>
2 #include<cstring>
3 #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
4 #define itn int
5 using namespace std;
6
7 const int N = 510;
8
9 int n, m;
10 int map[N][N];
11 bool st[10010];
12 int dist[N];
13
14 int dijkstra() {
15 memset(dist, 0x3f, sizeof dist);
16 dist[1] = 0;
17
18 for (int i = 1; i <= n; i++)
19 {
20 int t = -1;
21
22 for (int j = 1; j <= n; j++)
23 if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
24
25 st[t] = true;
26
27 for (int k = 1; k <= n; k++)
28 dist[k] = min(dist[k], dist[t] + map[t][k]);
29
30 }
31 if (dist[n] == 0x3f3f3f3f) return-1;
32 return dist[n];
33 }
34
35 int main() {
36 fast;
37
38 cin >> n >> m;
39
40 memset(map, 0x3f, sizeof map);
41
42 for (int j = 1; j <= m; j++)
43 {
44 int a, b, c;
45 cin >> a >> b >> c;
46 map[a][b] = min(map[a][b], c);
47 }
48
49 int t = dijkstra();
50
51 cout << t;
52
53 return 0;
54 }
dikstra算法时间复杂度为O(n^2) 主要耗时的步骤是从dist 数组中选出没有确定最短路径的节点中距离源点最近的点 t。
如果能在一组数中每次能很快的找到最小值，那么时间复杂度可以大大降低，这时候我们就能想到一种数据结构:优先队列
堆里存储距离和节点编号 pair<int,int>
优先队列定义 : priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶
1 #include <cstring>
2 #include <iostream>
3 #include <algorithm>
4 #include <queue>//堆的头文件
5
6 using namespace std;
7
8 typedef pair<int, int> PII;//堆里存储距离和节点编号
9
10 const int N = 1e6 + 10;
11
12 int n, m;//节点数量和边数
13 int h[N], w[N], e[N], ne[N], idx;//邻接表存储图
14 int dist[N];//存储距离
15 bool st[N];//存储状态
16
17 void add(int a, int b, int c)
18 {
19 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
20 }
21
22 int dijkstra()
23 {
24 memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
25 dist[1] = 0;
26 priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
27 heap.push({0, 1});//插入距离和节点编号
28
29 while (heap.size())
30 {
31 auto t = heap.top();//取距离源点最近的点
32 heap.pop();
33
34 int ver = t.second, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离
35
36 if (st[ver]) continue;//如果距离已经确定，则跳过该点
37 st[ver] = true;
38
39 for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
40 {
41 int j = e[i];
42 if (dist[j] > dist[ver] + w[i])
43 {
44 dist[j] = dist[ver] + w[i];
45 heap.push({dist[j], j});//距离变小，则入堆
46 }
47 }
48 }
49
50 if (dist[n] == 0x3f3f3f3f) return -1;
51 return dist[n];
52 }
53
54 int main()
55 {
56 scanf("%d%d", &n, &m);
57
58 memset(h, -1, sizeof h);
59 while (m -- )
60 {
61 int a, b, c;
62 scanf("%d%d%d", &a, &b, &c);
63 add(a, b, c);
64 }
65
66 cout << dijkstra() << endl;
67
68 return 0;
69 }
总结：
Dijkstra算法适用于求正权有向图中，源点到其余各个节点的最短路径。注意：图中可以有环，但不能有负权边
