一、最短路的分类
n 表示点的数量 m表示边的数量
1、单源最短路
求一个点到所有点的最短路
(1) 所有边权都是正数
①朴素的dijkstra算法 O（n^2）
时间复杂度和边数无关 适合稠密图（边数多）
适合边数是n^2级别的情况
②堆优化版的dijkstra算法O(mlogn)
适合边数是n级别的情况（节点多 边数少）
（2）存在负权边
①Bellman-Ford算法 O(nm)
②SPFA O(m) 对Bellman-Ford算法的优化
2、多源最短路
起点和终点都不确定，求任意两个点的最短路
Floyd算法 O(n^3)
二、朴素版Dijkstra算法
1、初始化距离
dis[1]=0 一号点到起点的距离为0，
dis[i]=+∞ 其余的点到起点的距离为无穷
2、迭代
集合s 当前已经确定最短路的点
循环n次 for i:n
迭代找到不在s中的距离最近的点 t
把t加入到s中
用t更新其他点的距离
更新也循环n次 所以总的时间复杂度是n^2;
（看1号点走到x的距离是否大于从1号点走到t，再从t走到x。如果大于则更新1号点到x点的距离）
3、本算法适合于稠密图 用邻接矩阵来存
注意：无向图和有向图的最短路是没有区别的
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];//邻接矩阵存储稠密有向图
int dis[N]; //表示确定的点的最短距离
bool vis[N];//这个点是否被访问过
int Dijkstra() {
memset(dis, 0x3f, sizeof(dis));//其余点初始化距离为无穷
dis[1] = 0;//起点初始化距离为0
for (int i = 1; i <= n; i++) {//首先要遍历N次每次确定一个节点
int t = -1;
for (int j = 1; j <= n; j++) {//第二个for是找出确定距离的点中的最小的节点
if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
t = j;
}
}
vis[t] = true;
for (int j = 1; j <= n; j++) {//第二个for 根据选中的节点 更新距离
dis[j] = min(dis[j], dis[t] + g[t][j]);
}
}
if (dis[n] == 0x3f3f3f3f)
return -1;
else return dis[n];
}
int main()
{
memset(g, 0x3f, sizeof(g));
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << Dijkstra() << endl;
return 0;
}
三、堆优化版的Dijkstra
为了实现在一堆数中找到最小的数 ->需要用堆实现
1、堆的实现
①手写堆 里面n个数
②优先队列 里面m个数 （复杂度稍微提高）
本算法适合稀疏图->存储方式使用邻接表
注意：用邻接表存储 不需要特殊处理重边
边的权不为1的时候邻接表加边模板
add(int a,int b,in c){
e[idx]=b;
ne[idx]=h[a];
wei[idx]=c;
h[a]=idx++;
}
基本思路
1.首先初始化起点的距离为0 其余点的距离为无穷
2.将起点加入到优先队列中 优先队列维护最小值
3.根据堆顶元素的权值和他能到达的点，更新其他点的距离，将更新距离后的点加入到队列中
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * N;
typedef pair<int, int> PII;
int n, m;
int h[N], e[M], wei[M], ne[M], idx;
bool vis[M];
int dis[N];
void add(int a, int b, int c) {//有权重的加边方式
e[idx] = b;
wei[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int Dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> pq;//小根堆 距离小的排在前面
pq.push(make_pair(0, 1));
while (pq.size()) {
PII now = pq.top();
pq.pop(); //直接根据已经知道的点和这个点到其他点的权重更新能到达的点的距离
int distance = now.first;
int ser = now.second;
if (vis[ser]) //如果这个点已经加入堆中过了 那么剩下的是冗余的 不可能是最短路
continue;
vis[ser] = true;
for (int i = h[ser]; i != -1; i = ne[i]) {
int j = e[i]; //j代表a->b的b 即ser能到达的点
if (dis[j] > dis[ser] + wei[i]) {
dis[j] = dis[ser] + wei[i];//当前的值可能是无穷 如果当前的值大于从ser点到它的值则更新
//这里的dis[ser]和distance是相等的
pq.push(make_pair(dis[j], j));//将其入队
}
}
}
if (dis[n] == 0x3f3f3f3f)
return -1;
else return dis[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << Dijkstra() << endl;
//system("PAUSE");
return 0;
}