引用一位老oier的话：
一道题如果边权没有负数，那么一定是在卡SPFA。这时候就用到了堆优化的Dijkstra;
写在前面：
多打代码！
最好都掌握，灵活变通
SPFA:
主要用于稀疏图和有负权边的图上
参考blog：
https://blog.csdn.net/sxy201658506207/article/details/78779045
（前向星版）
注：起点为1
1 #include <cstdio> 2 #include <algorithm> 3 4 #define MAXN 11111 5 #define MAXM 222222 6 #define INF 2000000000 7 8 int n, m, cnt, ans; 9 int q[MAXN];//队列 10 int p[MAXN];//用于打印解 11 int is_fuquan[MAXN];//用于判断负圈 12 13 int dis[MAXN], vis[MAXN]/*判断在不在队列中*/, head[MAXN]; 14 15 struct edge { 16 int y, val, next; 17 }e[MAXM];//前向星 18 19 void add_edge(int x, int y, int val) { 20 cnt++;//边的个数加一 21 e[cnt].y = y; 22 e[cnt].val = val; 23 e[cnt].next = head[x]; //当前边上一条同起点的边的编号为head[x] 24 head[x] = cnt; //当前边为最后一条以x为起点的边的编号 25 return ; 26 } 27 28 int main() { 29 scanf("%d%d", &n, &m); 30 for(int i = 1; i <= m; i++) { 31 int x, y, z; 32 scanf("%d%d%d", &x, &y, &z); 33 add_edge(x, y, z);//**双向边** 34 add_edge(y, x, z); 35 } 36 37 for(int i = 1; i <= n; i++) dis[i] = INF; //初始化 38 int l = 1, r = 1; 39 q[1] = 1; //起点入队 40 dis[1] = 0; 41 vis[1] = 1; 42 while(l <= r) { 43 int now = q[l]; 44 l++;//更新队首 45 vis[now] = 0; //注意不在队列中 要标记为0即 **重复入队** 46 for(int i = head[now]; i; i = e[i].next) { //遍历所有now的出边 (重点) 47 int y = e[i].y, val = e[i].val; 48 if(dis[y] > dis[now] + val) { //看now所有出边的终点 是否 需要更新 49 dis[y] = dis[now] + val; //更新长度 50 p[y] = i;//记录边 51 if(vis[y] == 0) { //若终边不在队中 52 q[++r] = y; 53 vis[y] = 1; //**y入队 标记为1** 54 if(++is_fuquan[y] > n) return 0;//这可以是其他题目中需要返回的值 55 //这个就是用于发现负圈时及时退出（希望写在应该bool 值的SPFA函数中，然后返回false 56 //因为 一个点在没有负环的情况下，最多只会有 n-1 个点与它相连 57 //若有负环，这个便会一直for 所以这样做 58 } 59 } 60 } 61 } 62 for(int i = 1; i <= n; i++) 63 printf("%d ", dis[i]); 64 return 0; 65 }
/*
4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
dijkstra:
可以解不带负权边的图，在稠密图上有很好性能
参考blog：
ps:出自oier : https://www.cnblogs.com/jason2003/p/7222182.html
过程:
先建立一个dis数组，dis[i]表示第i号点到源点（1号点）的估计值, 然后我们在建立一个临界矩阵，叫做：map，map[i][j]=v表示从i到j这条边的权值是v, dis初始值除了源点本身都是无穷大。源点本身都是0. 我们用minn记录距离1号点最短的路径，留着以后会用。
开始第二次更新时: 以minn相当于把2当源点，求所有点到它的最短路，加上它到真正的源点（1号点）的距离，就是我们要求的最短路。
注:时时更新minn的值
代码:用邻接矩阵实现dijksra：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int map[110][110];//这就是map数组，存储图
int dis[10010];//dis数组，存储估计值
int vis[10010];//vis[i]代表这个点有没有被当做源点去搜索过，1为有，0为没有。这样就不会重复搜索了。
int n,m;
void dijkstra(int u)//主函数，参数是源点编号
{
memset(dis,88,sizeof(dis));//把dis数组附最大值（88不是十进制的88，其实很大）
int start=u;//先从源点搜索
book[start]=1;//标记源点已经搜索过
for(int i=1;i<=n;i++)
{
dis[i]=min(dis[i],map[start][i]);//先更新一遍
}
for(int i=1;i<=n-1;i++)
{
int minn=9999999;//这就是刚才所说的minn
for(int j=1;j<=n;j++) {
if(vis[j]==0 && minn>dis[j])
{
minn=dis[j];
start=j;
}
}//找到离源点最近的点，然后把编号记录下来，用于搜索。
vis[start]=1;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],dis[start]+map[start][j]);//以新的点来更新dis。
}
}
int main()
{
cin>>n>>m;
memset(map,88,sizeof(map));
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
map[a][b]=c;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)
map[i][j]=0;
dijkstra(1);//以1为源点。
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
}
优化dijkstra：（堆）
朴素的这玩意貌似很慢大概O(n方)，堆优化应该只是取dis最小快了…吧
出自我自己
// Luogu P4779
1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 using namespace std; 5 #define MAXN 120000 6 #define MAXM 233333 7 #define INF 1000003647 8 9 using namespace std; 10 11 int n, m, S, cnt; 12 int head[MAXN], dis[MAXN], vis[MAXN]; 13 14 struct node { 15 int id, dis; //id表示点的编号 dis为在加入优先队列时的dis[id] 16 node(int id = 0, int dis = 0) : id(id), dis(dis) {} //构造函数 17 bool operator < (const node &x) const { //重载运算符 //只有堆是这样的 18 return dis > x.dis; //小根堆 注意 这里用>时 最后堆顶为dis最小的 和sort的comp相反 19 } 20 }; 21 22 priority_queue <node> q; //优先队列 堆 23 24 struct edge { 25 int y, val, next; 26 }e[MAXM]; 27 28 void add_edge(int x, int y, int val) { //链式前向星 加边 29 e[++cnt].y = y; 30 e[cnt].val = val; 31 e[cnt].next = head[x]; 32 head[x] = cnt; 33 return ; 34 } 35 //总是取最小的，无论它有没有被选 36 //注：最开始初始化正无穷！！ 37 //先放起点，并标记为已确定，再堆非空while（直到找完所有点的最短路） 38 //取出堆顶，先看它是不是确定的，若不是，就直接确定下来 ，然后遍历它的出边，并更新终点dis值（需比较），再放入堆 39 void dijkstra() { 40 for(int i = 1; i <= n; i++) dis[i] = INF;//初始化 41 q.push(node(S, 0)); //把起点加入 //加入编号&dis值 42 dis[S] = 0; // 初始化 43 while(!q.empty()) { 44 node tmp = q.top();//当前所有元素中dis最小的 //取出来的是个node 45 q.pop(); //删除堆顶元素 46 int now = tmp.id; //当前点编号 47 if(vis[now]) continue; //若now为已确定元素（已知最短路的点） 则不执行下面语句 48 vis[now] = 1; //标记为已确定 //因为是堆 所以直接是最短的 //所以没有必要再找一遍 49 for(int i = head[now]; i; i = e[i].next) { //遍历边 50 int y = e[i].y; 51 if(dis[y] > tmp.dis + e[i].val) { //更新y的dis 52 dis[y] = tmp.dis + e[i].val;//dis[now] 和 tmp.dis不一定是一样的哦，有可能它已经更新为一个更小的值了 53 q.push(node(y, dis[y])); //放入堆 54 } 55 } 56 } 57 return ; 58 } 59 60 int main() { 61 scanf("%d%d%d", &n, &m, &S); 62 for(int i = 1, x, y, z; i <= m; i++) { 63 scanf("%d%d%d", &x, &y, &z); 64 add_edge(x, y, z); 65 } 66 dijkstra(); 67 for(int i = 1; i <= n; i++) 68 printf("%d ", dis[i]); 69 }
需要注意的是：存在负权环路的图中不存在最短路（路径可以一直减少），SPFA算法可以用来判断图中是否有负权环路
多源最短路出门下走至floyd