最短路径
dijkstra：O(N^2),，单源最短路径，不能有负边.可以通过堆优化为O(nlogn+m)
//图的结构都用邻接表写
//第一种：最简单的加上记录路径
struct node{
int v;
int dis;
};
vector<node> G[maxn];
int pre[manx]; //最简单的一种pre写法（苦笑——
//输出过程
int dis[maxn]={0}; //记录起点与其他各点的最短距离
void outputdfs(int v,int st){
if(v==st){
cout<<st<<endl;
return;
}
outputdfs(pre[v],st);
cout<<v<<" ";
}
void dijkstra1(int st){
int numnode,numedge,x,y,diss;
cin>>numnode>>numedge;
for(int i=0;i<numedge;i++){
cin>>x>>y>>diss;
node a,b;
a.v=x;a.dis=diss;b.v=y;b.dis=diss;
G[x].push_back(b);
G[y].push_back(a); //无向图
}//以后可以直接写构造函数
fill(dis,dis+maxn,INF);
dis[st]=0; //
for(int i=0;i<numnode;i++) pre[i]=i; //初始化pre数组不要忘了！！！！
for(int i=0;i<numnode;i++){
int u=-1,numi=INF;
for(int j=0;j<numnode;j++){
if(vis[j]==0&&dis[j]<mini){
mini=dis[j];
u=j;
}
} //找点的过程
if(u==-1) return; //退出标志
vis[u]=1;
//这是第一阶段
for(int j=0;j<G[u].size();j++){
//更新与找到的这个点相连的点
int v=G[u][j].v;
if(vis[v]==0&&dis[v]<dis[u]+G[u][j].dis){
dis[v]=dis[u]+G[u][j].dis;
pre[v]=u;
}
}
}
}
堆优化的dijkstra算法（优先队列）
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=105;
const int INF=0x3fffffff;
typedef long long LL;
//优先队列优化的dijkstra算法 O(nlogm)
struct edge{
int from,to,dis;
edge(int a,int b,int c){
from=a;to=b;dis=c;
}
};
vector<edge> e[maxn];
struct node{
int id;
int dis; //这个节点到起点的距离
node(int a,int b){
id=a;dis=b;
}
bool operator <(const node &a)const{
return dis>a.dis; //重载小于符
}
};
int n,m;
int pre[maxn];
void print_path(int s,int t){
if(s==t) cout<<s<<endl;
print_path(s,pre[t]);
cout<<t<<" ";
}
void dijkstra(){
int s=1;
int dis[maxn];
bool done[maxn]; //标记节点i的最短路有没有找到
for(int i=1;i<=n;i++) {
dis[i]=INF;done[i]=false;
}
dis[s]=0;
priority_queue<node> q;
q.push(node(s,dis[s]));
while(!q.empty()){
node u=q.top();
q.pop();
if(done[u.id]) continue; //如果已经找到了！！丢弃已经找到最短路的节点
done[u.id]=true;
for(int i=0;i<e[u.id].size();i++){
edge y=e[u.id][i];
if(done[y.to]) continue; //丢弃已经找到最短路的邻居节点
if(dis[y.to]>y.dis+u.dis){
dis[y.to]=y.dis+u.dis;
q.push(node(y.to,dis[y.to]));
pre[y.to]=u.id;
}
}
}
printf("%d\n",dis[n]);
// print_path(s,n);
}
int main(){
while(~scanf("%d %d",&n,&m)){
if(n==0||m==0) break;
for(int i=0;i<n;i++) e[i].clear();
while(m--){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[a].push_back(edge(a,b,c));
e[b].push_back(edge(b,a,c));
}
dijkstra();
}
return 0;
}
有第二标尺的
边权标尺（花费等，至于边权！=距离）
int cost[maxn][maxn];
int c[maxn];
/*
struct node{
int v;
int dis;
};
vector<node> G[maxn];
int dis[maxn]={0}; */
void dijkstra2(int st){
fill(dis,dis+maxn,INF);
dis[st]=0;
fill(c,c+maxn,INF);
c[st]=0;
for(int i=0;i<numnode;i++){
int u=-1,mini=INF;
for(int j=0;j<numnode;j++){
if(vis[j]==0&&dis[j]<mini){
mini=dis[j];u=j;
}
}
if(u==-1) return ;
vis[u]=1;
//以上为第一阶段
for(int j=0;j<G[u].size();j++){
int v=G[u][j].v;
if(vis[v]==0){
if(dis[v]>dis[u]+G[u][j].dis){
dis[v]=dis[u]+G[u][j].dis;
c[v]=c[u]+cost[u][v];
}
else if(dis[v]==dis[u]+G[u][j].dis&&c[v]>c[u]+cost[u][v]){
c[v]=c[u]+cost[u][v]; //因为是花费，所以越小越好
}
}
}
}
}
点权（例如资源等）越多越好
int weight[maxn];
int w[maxn];
/*
struct node{
int v;
int dis;
};
vector<node> G[maxn];
int dis[maxn]={0}; */
void dijkstra3(int st){
fill(w,w+maxn,0); //注意不同：点权的其他不等于起点的都赋值位0，边权赋值位无穷大
w[st]=weight[st];
fill(dis,dis+maxn,INF);
dis[st]=0;
//初始化阶段
for(int i=0;i<numnode;i++){
int u=-1,mini=INF;
for(int j=0;j<numnode;j++){
if(vis[j]==0&&dis[j]<mini){
mini=dis[j];u=j;
}
}
if(u==-1) return ;
vis[u]=1;
//以上为第一阶段
for(int j=0;j<G[u].size();j++){
int v=G[u][j].v;
if(vis[v]==0){
if(dis[v]>dis[u]+G[u][j].dis){
dis[v]=dis[u]+G[u][j].dis;
w[v]=w[u]+weight[v];
}
else if(dis[v]==dis[u]+G[u][j].dis&&w[v]<w[u]+weight[v]){
w[v]=w[u]+weight[v]
}
}
}
}
}
路径条数
int num[maxn]; //就多这一个数组
/*
struct node{
int v;
int dis;
};
vector<node> G[maxn];
int dis[maxn]={0}; */
void dijkstra4(int st){
fill(num,num+maxn,0); //与点权一样：与起点不同的都赋值为0；起点为1
num[st]=1;
fiil(dis,dis+maxn,INF);
dis[st]=0;
for(int i=0;i<numnode;i++){
int u=-1,mini=INF;
for(int j=0;j<numnode;j++){
if(vis[j]==0&&mini>dis[j]){
mini=dis[j];u=j;
}
}
if(u==-1) return ;
vis[u]=1;
for(int j=0;j<G[u].size();j++){
int v=G[u][j].v;
if(vis[v]==0){
if(dis[v]>dis[u]+G[u][j].dis){
dis[v]=dis[u]+G[u][j].dis;
num[v]=num[u]; //继承
}
else if(dis[v]==dis[u]+G[u][j].dis){
num[v]+=num[u]; //加上
}
}
}
}
}
第二标尺不满足最优子结构时，需要改变算法，即不能在Dijkstra的算法过程中直接求出最优而是应该先求出所有的最优路径，然后选择第二标尺最优的那条路。所以采用Dijkstra+DFS的方法，Dijkstra求出所有的最优路径，DFS求出第二标尺最优的
所以改变是pre[maxn]---vector<int> pre[maxn]‘
vector<int> pre[maxn];
void dijkstra5(int st){
fill(dis,dis+maxn,INF);
dis[st]=0;
for(int i=0;i<numnode;i++){
int u=-1,mini=INF;
for(int j=0;j<numnode;j++){
if(vis[j]==0&&mini>dis[j]){
mini=dis[j];u=j;
}
}
if(u==-1) return ;
vis[u]=1;
//以上为第一阶段
//改变的是下面的第二阶段，在记录最优路径的时候
for(int j=0;j<G[u].size();j++){
int v=G[u][j].v;
if(dis[v]>dis[u]+G[u][j].dis){
dis[v]=dis[u]+G[u][j].dis;
pre[v].clear();
//先清空
pre[v].push_back(u);
}
else if(dis[v]==dis[u]+G[u][j].dis){
//如果距离一样 ，就压入
pre[v].push_back(u);
}
}
}
}
//接下来找出第二标尺最优的那个路径
//当画出这个路径时，会发现是一颗树的结构，根节点是终点，叶子节点都是起点(所以在有些情况下需要逆序），这样走下来找到最优标尺
//因为有多条路径，每次决定走哪条，所以用递归搜索+回溯的方法
//有一点绝对要注意，因为最后的叶子节点（起点）无法自己入数组，所以需要自己碰到叶子节点是把它push进来
vector<int> temppath,path; //一个用来临时存路径，一个用来存最优路径
int maxvalue;
void DFS(int st,int v){
if(v==st){
temppath.push_back(v);
//计算这条路径上的最优路径值
int value=0;
//eg：边权值和
for(int i=temppath.size();i>0;i--){ //这两个例子其实都满足最优子结构，可以直接用dijkstra来解，但是这个通用模板必须记住
//计算边权值和，边界时i>0;
int now=temppath[i],next=temppath[i-1];
value+=G[now][next].dis;
}
//eg:点权值和
for(int i=temppath.size();i>=0;i--){
//计算点权值和：边界为i>=0
int id=temppath[i];
value+=weight[id];
}
if(value>maxvalue){
maxvalue=value;
path=temppath;
}
//记录最优路径
//不要忘记弹出噢！！！
temppath.pop_back();
return;
//以及return噢！~
}
temppath.push_back(v);
for(int i=0;i<pre[v].size();i++){
DFS(st,pre[v][i]);
}
temppath.pop_back();
//也不要忘记弹出回溯噢！！！~
}
Bellman-ford：O(NM)，
对边进行遍历。不能有负权回路，但是能提示，可用循环队列。
但是如果从原点无法到达负环的话，是不会有有影响的。
可以处理负边权，再进行以此松弛操作既可以判断是不是存在负环 、所有的边进行操作，看能不能通过这条边来进行优化
最短路径树：层数不超过V，源点s作为根节点，其他节点按照最短路径的节点顺序连接
注意求路径数的时候，vector<int> pre[maxn]要改为set<int> pre[maxn]
bool ford(int s){
fill(dis,dis+maxn,INF);
dis[s]=0;
//n是节点个数，因为最后是一棵树，所以边数为n-1即一共只需要n-1次循环
for(int i=0;i<n-1;i++){
for(int j=0;j<n;j++){
for(int z=0;z<adj[j].size();z++){
int v=adj[j][z].v;
int di=adj[j][z].dis;
if(di+dis[j]<dis[v]) dis[v]=dis[j]+di;
}
}
}
//再遍历以下所有的边，看还能不能松弛
for(int i=0;i<n;i++){
for(int j=0;j<adj[i].size();j++){
int v=adj[i][j].v;
int di=adj[i][j].dis;
if(dis[v]>dis[i]+di) return 0;
}
}
return 1;
}
//如果用ford算法求解路径的话
//需要用
set<int> pre[maxn];
int num[maxn];
if(dis[v]>dis[j]+di){
dis[v]=dis[j]+di;
num[v]=num[j]; //直接覆盖
pre[v].clear();
pre[v].insert(j);
}
else if(dis[v]==dis[j]+di){
pre[v].insert(j); //先插入
num[v]=0; //先付0
for(set<int>::iterator it=pre[v].begin();it!=pre[v].end();it++) num[v]+=num[*it]; //不是直接加*it啊
}
SPFA：ford的队列实现，单源最短路径，与BFS的区别：出了队的可以再次入队。
对ford的优化：只有最短路改变了的才可能继续改变其他的节点的最短路，所以没必要访问全部
判断有无负环的方法是计算每个节点的入队次数，如果入队次数超过n就存在负环了
int vis[maxn];//这是用来记录是不是在队列里面的
int num[maxn]; //记录入队次数（如果说明不存在负环就不需要这个）
bool spfa(int s){
fill(dis,dis+maxn,INF);
dis[s]=0;
vis[s]=1;
num[s]++; //入队次数+1
queue<int> q;
q.push(s);
while(!q.empty()){
int top=q.front();
q.pop();
vis[top]=0; //出队了
//接着访问这个节点的所有邻接边
for(int i=0;i<adj[top].size();i++){
int v=adj[top][i].v;
int diss=adj[top][i].dis;
if(dis[v]>dis[top]+diss) {
dis[v]=dis[top]+diss;
//先松弛，然后判断能不能入队
if(!vis[v]){
q.push(v);
vis[v]=1;
num[v]++;
if(num[v]>=n) return 0;
}
}
}
}
return 1;
}
Floyd：O(N^3),全源最短，可以处理负边权，可以判断负环
负环判断：初始化所有的dp[i][i]=0后，如果结束时dp[i][i]<0，那么就存在负环
//n在200以内
//在main()函数里面先执行：
for(int i=0;i<n;i++) dis[i][i]=0;
//然后是函数体
void floyd(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。个人觉得LLL优化每次要求平均值，不太好，为了简单，我们可以之间用c++STL里面的优先队列来进行SLF优化。
原文：https://www.cnblogs.com/shirlybaby/p/12489284.html