朴素Dijskra算法
时间复杂度：,适用于稠密图，需要用邻接矩阵来存储。
算法描述
设起点为s,dist[v] 表示起点到v点的最短距离。
a)初始化 dist[v]=INF(v!=s),dist[s] = 0这里一共有n个点，第一个点(起点)初始化为0，其余都初始化为inf。
for(int i=1;i<=n;i++)对一个一个点进行遍历
1.在没有被访问过的节点中，找一个顶点u，使得dist[u]是最小的
2.u标记为已经确定的最短路径
3.For与u相连的每一个未确定的最短路径节点v
if(dist[u]+w[u][v] < dist[v]){
dist[v] = dist[u]+w[u][v];
}
算法结束。
图例
假如有以下图：
初始化：
第一轮：
中间场：
此时要再dist数组中找到一个具体起点最短的点，这里是2号点，要把2好点设置为已经确定是最小路径了(如何证明？百度自己搜doge)。
第二轮：
接着遍历与2号节点相连的并且没有确定最短路径的点(这里是3、5)，这里因为d[2]+w[2][3]<d[3]。d[2]+w[2][5]<d[5]。所以更新3和5号点。
中间场：
此时还未确定最短路径的还有3、4、5号点，最小的是3号点。将3号点距离确定为最小。
第三轮：
查看与3好点相连的还没有确定最短路径的点。即4、5号点，更新了4号点。
中间场：
再剩下的没有确定最短路径的点中找到最小的，这里是5号点，将其设置为确定状态。
第四轮：
找到剩余没有确定最短路径的点，即4号点，将其设置为最短的。
算法结束。
例题：
第一行包含整数 n和 m。
接下来 mm 行每行包含三个整数 x,y,z表示存在一条从点 x到点 y 的有向边，边长为 z。
输出格式:
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
int g[N][N];//图的邻接矩阵
int dist[N];//每个点距离起点的最短距离
bool st[N];//每个点是否已经确定最短距离
int n,m;int dijkstra(int start){memset(dist,0x3f,sizeof(dist));dist[start] = 0;//st[start] = true;这个不需要，因为后面是从1号遍历到n号，所以第一次选没确定的要选上起点for(int i=0;i<n;i++){int t = -1;//t来存储剩余的没有确定最短轮径的最小的节点。for(int j=1;j<=n;j++){if(!st[j] && (t==-1 ||dist[t]>dist[j])){ //并上t==-1是如果t==-1就不执行后面的了t = j; //因为在一个集合中，我们不能确定哪一个点还没有被确定最短路径，所以让他自己遍历，遍历到第一个就是t的值}}st[t] = true;for(int j=1 ; j<=n ;j++){if(dist[j]>dist[t] + g[t][j]){dist[j] = dist[t] + g[t][j];}}}if(dist[n]==0x3f3f3f3f){return -1;}else{return dist[n];}
}int main(){scanf("%d%d",&n,&m);memset(g,0x3f,sizeof(g));for(int i=0;i<m;i++){//存储图int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b] = min(g[a][b],c);//有多条边，只要保存长度最小的那一条。}int res = dijkstra(1);cout<<res;return 0;
}堆优化版Dijskra算法
时间复杂度：，适用于稠密图，用邻接表来存储。
优化点：此时点数很多，如果载用邻接矩阵存储显然不现实，所以需要用邻接表。上面朴素版的是直接循环的，在第二层循环中找到还没有确定最短路径的最小的点是O(n)。如果用优先队列则只需要O(1)。只是建立和维护队列需要O(logn)。
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 150009;
int h[N],e[N],ne[N],w[N],dist[N],idx,n,m;
bool st[N];
void add(int a,int b,int c){e[idx] = b;ne[idx] = h[a];h[a] = idx;w[idx] = c;idx++;
}int dijkstra(int start){memset(dist,0x3f,sizeof(dist));dist[start] = 0;priority_queue<PII,vector<PII>,greater<PII> > heap;heap.push({0,start});//这里把编号放在第二位，因为默认比较的时候是比较pari的第一位。while(!heap.empty()){PII t = heap.top();heap.pop();int ver = t.second,distance = t.first;if(st[ver]) continue;st[ver] = true;for(int i=h[ver];i!=-1;i=ne[i]){int j = e[i];if(dist[j]>distance+w[i]){dist[j] = distance+w[i];heap.push({dist[j],j});}}}if(dist[n]==0x3f3f3f3f){return -1;}else{return dist[n];}
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));for(int i=0;i<m;i++){//存储图int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int res = dijkstra(1);cout<<res;return 0;
}Bellman-Ford
时间复杂度：
可以解决存在负全边的最小路径问题。
算法描述：
//设置s为起点，dist[v]为s到v的最短距离,pre[v]为v的前驱。w[j]为边j的长度，且j连接u、v。
//初始化：dist[s]=0,dist[v]=inf(v!=s),pre[s]=0
//For(i = 1;i<n;i++)
//For(j=1;j<=M;j++)
// if(dist[u[j]] + w[j] < dist[v[j]]) u[j]、v[j]分别是这条边连接的两个起点和终点
// {
// dist[v[j]] = dist[u[j]] + w[j];
// pre[v[j]] = u[j];
// }
图例：
假如给出这些边：
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
第一轮第一次遍历边：
不用更新
第一轮第二次遍历边：
更新节点2的dist
第一轮第三次遍历边：
更新节点5的dist
第一轮第四次遍历边：
不满足条件。
第一轮第五次遍历边：
不满足条件
第二轮第一次遍历边：
更新3号节点dist
...
最后会得到最短路径。
853. 有边数限制的最短路 - AcWing题库
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510,M=10009;
int n,m,k;
struct Edge{int a,b,w;
}edgs[M];int dist[N],copydist[N];int Bellman_Ford(int start){memset(dist,0x3f,sizeof(dist));dist[start] = 0;for(int i=0;i<k;i++){这里最多循环到k是因为要求：最多经过 k条边的最短距离,这就只需要最多k次就可以完成。memcpy(copydist,dist,sizeof(dist));//这里备份的原因是因为最长的是k,如果一层循环中在刚刚更新的基础上再次循环边，就可能出现超过k的情况for(int j=1;j<=m;j++){int a = edgs[j].a,b=edgs[j].b,w=edgs[j].w;//注意这里的a、b是节点编号，w是这条边的权重dist[b] = min(copydist[a]+w,dist[b]);//注意这里是用原来的dist即备份过的copydist来更新此次的dist}}if(dist[n]> 0x3f3f3f3f /10) return 0;else return dist[n];}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int a1,b1,c1;scanf("%d%d%d",&a1,&b1,&c1);edgs[i] = {a1,b1,c1};}int t = Bellman_Ford(1);if(t==0) printf("impossible");else{printf("%d",t);}return 0;
}SPFA
时间复杂度：一般，最坏：
正常情况下Bellman-Ford算法(不是限制了边数),最主要的就是更新dist。
即：dist[b] = min(dist[a]+w,dist[b]);
我们仔细想一下，好像只有b的前驱a变小了，那么b才有可能变小。
那么我们可以用一个队列来存储所有“变小”的节点，然后每次再从队列中拿出这个点，只更新这个点的指向的边。
算法描述：
queue<--1
while queue非空
1. t<--q.front();
q.pop();
2.更新t的所有出边 t-->b
queue<--b
851. spfa求最短路 - AcWing题库
这里初始化dist为最大值时有点问题，先自定义一个INF然后用fill这样安全一点。
如果初始化0或者-1可以直接用memset。
#include<iostream>
#include<queue>
#include<cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
const int INF = 1000000000;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];//用来判断这个点是否已经在队列中void add(int a,int b,int c){e[idx] = b;ne[idx] = h[a];h[a] = idx;w[idx] = c;idx++;
}int spfa(int start){fill(dist,dist+N,INF);dist[start] = 0;queue<int> q;q.push(start);st[start] = true;while(!q.empty()){int t = q.front();q.pop();st[t] = false;for(int i = h[t];i != -1 ;i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if(!st[j]){q.push(j);st[j] = true;}}}}if(dist[n] == INF) return 0;return dist[n];
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int res = spfa(1);if(res == 0) printf("impossible");else{printf("%d",res);}return 0;
}判断是否存在负环
我们的SPFA算法也可以判断一个图中是否存在负数环。
求解思想如下：
我们可以增加一个数组来记录当前节点距离起点的边数，我们每次更新dist数组时有dist[t]=dist[j]+w[i]，此时我们也更新cnt[t] = cnt[j] + 1;这里cnt[v]存储的是点v到起点的最短路径的边的数量。又因为只要有负数边，那么就一定会更新，一个整数加一个负数一定小于原来的数。因为原点1不一定可以到达负边的圈，所以需要把所有点都入队。
#include<iostream>
#include<queue>
#include<cstring>
#include <algorithm>
using namespace std;
const int N = 2009,M=10009;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int cnt[N];void add(int a,int b,int c){e[idx] = b;ne[idx] = h[a];h[a] = idx;w[idx] = c;idx++;
}int spfa(){queue<int> q;for(int i=1;i<=n;i++){q.push(i);st[i] = true;}while(!q.empty()){int t = q.front();q.pop();st[t] = false;for(int i = h[t];i != -1 ;i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] +1;if(cnt[j]>=n) return 1;if(!st[j]){q.push(j);st[j] = true;}}}}return 0;
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int res = spfa();if(res) printf("Yes\n");else{printf("No");}return 0;
}
