最短路算法总结
一、目录
1.Floyd（n^3) n：点数
2.dijikstra( n^2 -> mlogn) n：点数 m:边数 （不理解复杂度）
3.bellman-ford(nm) n: 点数 m:边数
4.spfa(Km) K:约为2的常数 m:边数
5.Johnson (nmlogm) （不理解复杂度）
二、实现的代码
1.floyd 全源最短路（可以解决负权边，但不能解决负权回路）
代码的核心：从第i点到第j点的过程中，寻找是否有第k点（k ！= i && k ！= j）作为中转点，使得i点和j点之间的最短路可以更新，从而完成代码。
要注意：k要放在最外层循环（本质与动规状态转移有关）否则对于一些神奇的数据点，会出错！！！
#include<bits/stdc++.h>
using namespace std;
#define N 200//基本为最大数据范围
int f[N][N];//两个点之间的最短距离
int main(){
int n, m;//n为点的数目，m为边的数目
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof(f));//初始化为无穷大
for(int i = 1; i <= n; ++ i)
f[i][i] = 0;//自己到自己的距离初始化为0
for(int j = 1; j <= m; ++ m){
scanf("%d%d%d", &x, &y, &z);
if(z < f[x][y]) f[x][y] = f[y][x] = z;
}
for(int k = 1; k <= n; ++ k)//k必须在最外层循环，作为动态转移的状态
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
if(i != k && i != j && k != j && f[x][k] + f[k][y] < f[x][y]) f[x][y] = f[y][x] = f[x][k] + f[k][y];
f[a][b]即为a,b两点之间的最短距离
return 0;
}
2.dijikstra 单源最短路（不能解决负权边）
代码的核心：松弛操作若能实现，将点加入到优先队列中，每次取出距离起点最短距离的点进行拓展，并且保证每个点只进行一次遍历它所有相邻的点。
此处代码直接用堆优化，因为不优化的dijikstra意义不大（时间复杂度高）
注意：压入队列时，要压边权的相反数！（默认大根堆）
#include<bits/stdc++.h>
using namespace std;
const int N = 1050;//基本为最大数据范围
int dis[N];
bool vis[N];
vector<pair <int , int> >vec[N];
priority_queue<pair <int , int> >que;//大根堆
void dijikstra(int x){
que.push(make_pair(0, x));
dis[x] = 0;
while(!que.empty()){
int u = que.top().second;
que.pop();
if(vis[u]) continue;
vis[u] = 1;
int len = vec[u].size();
for(int i = 0; i < len; ++ i){
int v = vec[u][i].first;
int w = vec[u][i].second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
que.push(make_pair(-dis[v], v));//压
}
}
}
return ;
}
int main(){
int x, y, v;
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i){
scanf("%d%d%d", &x, &y, &v);
vec[x].push_back(make_pair(y, v));
vec[y].push_back(make_pair(x, v));
}
int center;
scanf("%d", ¢er);
memset(dis, 63, sizeof(dis));
dijikstra(center);//求出以center为起点的各点的最短路，存储在dis数组中
printf("%d", dis[目标点]);
return 0;
}
3.bellman-ford 单源最短路（能解决负权边,不能解决负环，但可以判断负环）
代码核心：跑n次循环，每次跑m条边的首尾点之间的距离，如果能更新就及时更新。
#include<bits/stdc++.h>
using namespace std;
#define N 3050
struct Edge{
int u, v;
int w;
}edge[N];//结构体数组用来存边
int dis[N];
int main(){
int U, V;//起点和终点
scanf("%d%d", &U, &V);
memset(dis, 63, sizeof(dis));
dis[U] = 0;//初始化
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
scanf("%d%d%d", &edge[i].u, &edge[i].v, edge[i].w);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
if(dis[edge[j].u] + edge[j].w < dis[edge[j].v])
dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
if(dis[edge[j].v] + edge[j].w < dis[edge[j].u])
dis[edge[j].u] = dis[edge[j].v] + edge[j].w;
}
for(int j = 1; j <= m; ++ j)
if(dis[edge[j].u] + edge[j].w < dis[edge[j].v] || dis[edge[j].v] + edge[j].w < dis[edge[j].u])
printf("存在负环！！！")
printf("%d", dis[V]);
return 0;
}
4.spfa求单源最短路（能解决负权边，不能解决负环，可判断负环）
代码核心：用队列优化后的bellman-Ford算法，省去了冗余的循环，大大极高运行效率。
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
vector<pair<int, int> >vec[N];
queue<pair<int, int> >que;
int dis[N], d[N];//d[N]为走最短路到达某点所需步数
bool vis[N];
int spfa(int s)
{
memset(dis, 63, sizeof(dis));
dis[s] = 0;
vis[s] = 1;
que.push(make_pair(0, s));
while(!que.empty())
{
int u = que.front().second;
vis[u] = 0;
que.pop();
for(int i = 0; i < vec[u].size(); ++i){
int v = vec[u][i].first;
int w = vec[u][i].second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
d[v] = d[u] + 1;
if(d[v] >= n) return 1;//若无负环，走最短路到达某点最多用n-1条边
if(!vis[v]){
vis[v] = 1;
que.push(make_pair(dis[v], v));
}
}
}
}
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
int x, y, z;
for(int i = 1; i <= m; ++i){
scanf("%d%d%d", &x, &y, &z);
vec[x].push_back(make_pair(y, z));
vec[y].push_back(make_pair(x, z));
}
int U, V;//U:起点 V：终点
scanf("%d%d", &U, &V);
int judge = spfa(U);
if(judge == 1) puts("存在负环！！！")
else printf("%d", dis[V]);
return 0;
}
5.johnson全源最短路（能解决负权边，不能解决负环，可以判断负环）
代码关键：bellman-ford与dijikstra的配合使用，大数据范围下优于spfa算法跑n次。
转载【洛谷日报#242】Johnson 全源最短路径算法学习笔记
链接：https://zhuanlan.zhihu.com/p/99802850
练习题：P5905 【模板】Johnson 全源最短路
链接：https://www.luogu.com.cn/problem/P5905
建议先看笔记，后做题，下面是本题题解
#include<bits/stdc++.h>
using namespace std;
#define N 3005
int h[N], vis[N];
long long dis[N];
struct Edge{
int u, v;
int w;
}edge[N * 2];//结构体数组用来存边
vector<pair <int , int> >vec[N];
priority_queue<pair <long long , int> >que;//大根堆
void dijikstra(int x){
memset(vis, 0, sizeof(vis));
que.push(make_pair(0, x));
dis[x] = 0;
while(!que.empty()){
int u = que.top().second;
que.pop();
if(vis[u]) continue;
vis[u] = 1;
int len = vec[u].size();
for(int i = 0; i < len; ++ i){
int v = vec[u][i].first;
int w = vec[u][i].second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
que.push(make_pair(-dis[v], v));
}
}
}
return ;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
int x, y, z;
for(int i = 1; i <= m; ++ i){
scanf("%d%d%d", &x, &y, &z);
edge[i].u = x;
edge[i].v = y;
edge[i].w = z;
}
for(int i = 0; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
if(h[edge[j].u] + edge[j].w < h[edge[j].v])
h[edge[j].v] = h[edge[j].u] + edge[j].w;
}
for(int j = 1; j <= m; ++ j)
if(h[edge[j].u] + edge[j].w < h[edge[j].v]){
puts("-1");
return 0;
}
for(int i = 1; i <= m; ++ i)
vec[edge[i].u].push_back(make_pair(edge[i].v, edge[i].w + h[edge[i].u] - h[edge[i].v]));
for(int i = 1; i <= n; ++ i)
dis[i] = 1e9;
for(int i = 1; i <= n; ++ i){
dijikstra(i);
long long tot = 0;
for(int j = 1; j <= n; ++ j){
if(dis[j] == 1e9) tot += j * 1e9;
else tot += j * (dis[j] + h[j] - h[i]);
dis[j] = 1e9;
}
printf("%lld\n", tot);
}
return 0;
}