https://ac.nowcoder.com/acm/contest/12606/H
大一就学了的东西但是一直没有系统总结过，正好碰到一个最短路题目直接开干。
Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)
BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度O(VE)
SPFA：适用于权值有负值，且没有负圈的图的单源最短路径，论文中的复杂度O(kE)，k为每个节点进入Queue的次数，且k一般<=2，但此处的复杂度证明是有问题的，其实SPFA的最坏情况应该是O(VE).
Floyd：每对节点之间的最短路径。
先给出结论：
(1)当权值为非负时，用Dijkstra。
(2)当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。
(3)当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。
(4)SPFA检测负环：当存在一个点入队大于等于V次，则有负环
spfa
时间复杂度 O ( k E ) O(kE) O(kE)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
优点：
1.适用范围广。
2.能够计算负权图问题。
3.能够判断是否有负环 (即：每跑一圈，路径会减小，所以会一直循环跑下去)。
算法思想：
1.设立一个先进先出的队列用来保存待优化的结点。
2.优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。
3.这样不断从队列中取出结点来进行松弛操作，直至队列空为止
判断负环：如果有一个点进入队列次数超过n次则有负环。
运用：实际上spfa相当于一个用队列优化的Bellman-Ford，时间复杂度很玄学，最坏情况下时间复杂度就退化为的
O
(
V
E
)
O(VE)
O(VE)复杂度。
在正边的时候有可能会被卡，可以用于负边权存在时的最短路，正边时还是建议用堆优化后的迪杰斯特拉。（但是它好写，而且适用范围广，蓝桥杯这种可以骗分。）
代码（使用vector存储邻接表）
#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=100005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int n,m;
struct edge{
int u,v,w;//出发点，目标点，距离
}ed[maxn];
vector<edge> g[maxn];//邻接表
int vis[maxn],dis[maxn];//标记i是否在队列中，起始点到i点的距离
void sqfa(int s)
{
queue<int> q;
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));//初始化
q.push(s);//起始点
dis[s] = 0;
vis[s] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = 0;i < g[x].size() ;i++){
edge nx = g[x][i];
//如果更新的结果更好，进行松弛操作，将下一个点距离更新，并加入队列
if(dis[nx.v] > dis[x] + nx.w){
dis[nx.v] = dis[x] + nx.w;
if(!vis[nx.v]){
q.push(nx.v);
vis[nx.v] = 1;
}
}
}
}
}
int main()
{
cin>>n>>m;
int u,v;
for(int i = 1 ;i <= m ;i++){
cin>>u>>v;
edge e1,e2;
e1.u = e2.v = u;
e1.v = e2.u = v;
e1.w = e2.w = 1;
g[u].push_back(e1);
g[v].push_back(e2);
}
sqfa(1);
cout<<dis[n]-1<<endl;
return 0;
}
Dijkstra
普通的迪杰斯塔拉就懒得在写了，主要是它的堆优化。
不优化的时候时间复杂度是
O
(
n
2
)
O(n^2)
O(n2)，优化后可以到
O
(
m
l
o
g
n
)
O(mlog_n)
O(mlogn)
用堆维护最小的dis节点，就不用每次都
O
(
n
)
O(n)
O(n)的查询了。c++的优先队列适用队实现的，直接优先队列就ok。
#include<bits/stdc++.h>
#include<iostream>
#include <stdio.h>
using namespace std;
const int maxn=100005;
const int base=131;
typedef long long ll;
#define pi acos(-1)
#define INF 0x3f3f3f3f
#define mod 998244353
const int inf=1<<30;
int n,m;
struct edge{
int u,v,w;//出发点，目标点，距离
}ed[maxn];
vector<edge> g[maxn];//邻接表
int vis[maxn],dis[maxn];//标记i是否在队列中，起始点到i点的距离
priority_queue< pair<int,int> > q;//大顶队，first为排序依据，存距离，second存对应的节点
void dil(int s)
{
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));//初始化
q.push(make_pair(0,s));//起始点
dis[s] = 0;
while(!q.empty()){
int x = q.top().second;
q.pop();
vis[x] = 1;
for(int i = 0;i < g[x].size() ;i++){
edge nx = g[x][i];
//如果更新的结果更好，进行松弛操作，将下一个点距离更新，并加入队列
if(dis[nx.v] > dis[x] + nx.w){
dis[nx.v] = dis[x] + nx.w;
q.push(make_pair(-dis[nx.v],nx.v));//因为是大顶堆，存相反数
}
}
}
}
int main()
{
cin>>n>>m;
int u,v;
for(int i = 1 ;i <= m ;i++){
cin>>u>>v;
edge e1,e2;
e1.u = e2.v = u;
e1.v = e2.u = v;
e1.w = e2.w = 1;
g[u].push_back(e1);
g[v].push_back(e2);
}
dil(1);
cout<<dis[n]-1<<endl;
return 0;
}