一、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 }