稠密图用邻接矩阵
稀疏图用邻接表
最短路问题
只有一个起点是单源
多个起点是多源
n是点的数量，m是边的数量
朴素Dijkstra算法的时间复杂度和边数无关，适合稠密图（边数较多时），m和n ^ 2一个级别时
堆优化版的Dijkstra算法适用于稀疏图，n和m一个级别
SPFA算法是对Bellman- Ford算法进行了优化
但有些问题是SPFA算法无法解决的，经过不超过k条边的最短路，只能用Bellman- Ford算法
Dijkstra基于贪心
Bellman- Ford基于离散数学
Floyd基于动态规划
==================================
然后先讲朴素Dijkstra，求的是从1号点到其他所有点的最短距离
基于贪心
1.初始化距离
首先1号点到自己的距离是0，其他点到1号点的距离是正无穷
2.循环n次
定义一个集合S，集合S里面存的是当前已经确定最短距离的点
然后每次循环，找到不在S中的，距离最近的点t
把t加进S里面
用t来更新其他所有点的距离
如何更新呢？
看一下从t出去的所有边，组成的路径能不能更新其他点的距离
比如t可以走到x
然后就看从起点到x的距离，能不能用从起点到t的距离更新
每一次循环都可以确定一个点的最短距离，那么循环n次的话，就可以确定n个点到起点的最短距离
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 510; 4 int g[N][N]; //稠密图用邻接矩阵 5 int dist[N]; //表示从1号点走到这个点的距离 6 bool st[N]; //表示每个点的最短路是否确定 7 int n, m; 8 int dijkstra() { 9 //1.初始化距离 10 memset(dist, 0x3f, sizeof(dist)); 11 dist[1] = 0; 12 //2.遍历n次 13 for (int i = 0; i < n; i++) { 14 int t = -1; 15 for (int j = 1; j <= n; j++) { //遍历所有点 16 if (!st[j] && (t == -1 || dist[t] > dist[j])) { 17 t = j; 18 } 19 } 20 if (t == n) { 21 break; 22 } 23 st[t] = true; //加进S 24 for (int j = 1; j <= n; j++) { //用这个点更新其他点 25 dist[j] = min(dist[j], dist[t] + g[t][j]); 26 } 27 } 28 if (dist[n] == 0x3f3f3f3f) { 29 return -1; 30 } 31 return dist[n]; 32 } 33 int main() { 34 cin >> n >> m; 35 memset(g, 0x3f, sizeof(g)); //存在重边和自环 36 while (m--) { 37 int a, b, c; 38 cin >> a >> b >> c; 39 g[a][b] = min(g[a][b], c); 40 } 41 cout << dijkstra() << endl; 42 return 0; 43 }