解决图论问题中的最短路径问题一般有四种算法，分别是Floyd算法、Dijkstra算法、Bellman-Ford算法和SPFA算法，下面介绍一下这几种算法的模板和原理用途。
Floyd算法
原理：Floyd本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i到j的最短路径。
用途：Floyd算法是求解多源最短路时通常选用的算法，经过一次算法即可求出任意两点之间的最短距离，并且可以处理有负权边的情况（但无法处理负权环）。时间复杂度为O(n3)。
代码框架：
#define N 100
const int INF = 0x3f3f3f3f;
int d[N][N];
// 代码初始化,共有n个顶点
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
d[i][j] = i == j ? 0 : INF;
}
}
// 将每条边的值加入到dis中去，这里不再赘叙
// Floyd算法
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
Dijkstra算法
原理：将结点分成两个集合：已确定最短路长度的点集（记为S集合）的和未确定最短路长度的点集（记为T集合）。一开始所有的点都属于T集合。
初始化dis(S) = 0，其他点的S均为INT_MAX。
然后重复这些操作：
-
从T集合中，选取一个最短路长度最小的结点，移到S集合中。
-
对那些刚刚被加入S集合的结点p的所有出边执行松弛操作。松弛操作即更新dis(T)的值，具体公式为：dis(T) = min(dis(T), dis(p) + w(p)(T))。
直到T集合为空，算法结束。
用途：基于贪心思想的一种求解 非负权图 上单源最短路径的算法。暴力的话O(n * n)。
代码框架：
// 假设共有n个节点
#define N 100
vector> w; // 储存每条边的权重
int dis[N]; // 储存开始节点到其他节点的最短距离
bool s[N]; // 储存已找到最短路径的节点
int dijkstra(int x, int des){ // 假设x节点为开始节点,des目的节点
// 初始化dis
memset(dis, 0x3f, sizeof(dis));
dis[x] = 0;
for(int i = 0; i < n; i++){
int p = -1; // 本次循环加入到S集合的节点
for(int j = 0; j < n; j++){ // 在集合T中寻找距离最小的节点
if(!s[j] && (p == -1 || dis[p] > dis[j])){
t = j;
}
}
//用p更新其他节点到开始节点x的最短距离
for(int j = 0; j < n; j++){
dis[j] = minx(dis[j], dis[p] + w[p][j]);
}
s[p] = true;
}
return dis[des];
}
Bellman-Ford算法
原理：逐基于动态规划，遍的对图中每一个边去迭代计算起始点到其余各点的最短路径（松弛操作），执行n - 1遍，最终得到起始点到其余各点的最短路径。
用途：Bellman–Ford 算法是一种基于松弛（relax）操作的单源最短路算法，可以处理负权边与负权回路。对于一个不包含负权环的V个点的图，任意两点之间的最短路径至多包含V-1条边。如果存在负权环，每次在负权环上走一圈都会使环上的每一个点的距离减少，因此不存在最短路径。时间复杂度为O(nm)，其中n为节点个数，m为边数。
可以解决边数限制的最短路径问题，SPFA无法代替。
代码框架：
// 假设共有n个节点，m条边
struct Edge { // 边u表示出点，v表示入点，w表示边的权重
int u, v, w;
}edges[m];
int dis[100]; // 储存开始节点到其他节点的最短距离
int Bellman_Ford(int start, int des){ // 开始节点为start，结束节点为des
memset(dis, 0x3f, sizeof(dis));
dis[start] = 0;
for(int i = 0; i < n; i++){ // 迭代n 次
for(int j = 0; j < m; j++){
if(i == n - 1 && dis[edges[i].v] > dis[edges[i].u] + edges[i].w){// 判断是否出现负权回路
// 最短距离发生更新，说明存在负权回路，返回-1
return -1;
}
dis[edges[j].v] = min(dis[edges[j].v], dis[edges[j].u] + edges[j].w);
}
}
return dis[des] > 0x3f3f3f3f / 2 ? -1 : dis[des];
}
SPFA算法
原理：初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。算法的流程为：
-
将除源点之外的所有的点当前距离初始化为无穷，并标记为未入队。源点的当前距离为0，将源点入队。
-
取出队首u，遍历u的所有出边，检查是否能更新所连接的点v的当前距离。如果v的当前距离被更新并且v不在队中，则将v入队。重复该操作直到队列为空。
-
检查是否存在负权环的方法为：记录一个点的入队次数，如果超过n-1次说明存在负权环，因为最短路径上除自身外至多n-1个点，故一个点不可能被更新超过n-1次。
用途：SPFA是队列优化的Bellman-Ford算法，因此用途与Bellman-Ford算法用途相同，但是时间复杂度更低。平均复杂度O(m)，最坏复杂度O(n * m)。
代码框架：
// 假设共有n个节点，m条边
#define N 100
struct Edge { // v表示出边，w表示边的权重
int v, w;
};
vector e[n]; // 与各个节点相连的边
int dis[N]; // 储存开始节点到其他节点的最短距离
bool s[N]; // 判断节点是否在队列中
int cnt[N]; // 记录边数
int spfa(int start, int des){ // 开始节点为start，结束节点为des
memset(dis, 0x3f, sizeof(dis));
dis[start] = 0;
queue q;
q.push(start);
s[start] = true;
while(!q.empty()){
int u = q.front();
q.pop();
s[u] = false;
for(auto &ed : e[u]){ // 遍历节点p能直接到达的节点,松弛操作
int v = ed.v, w = ed.w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v] >= n){ // 出现负权回路
return -1;
}
if(!s[v]){
q.push(v);
s[v] = true;
}
}
}
}
return dis[des] > 0x3f3f3f3f / 2 ? -1 : dis[des];
}
总结
（1）单源最短路：给定V中的一个顶点，称为源。要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 问题。
所有边权都是正数：
朴素Dijkstra算法 O(n^2) 适合稠密图，贪心思想
堆优化版的Dijkstra算法 O(mlogn)适合稀疏图，贪心思想
存在负权边：
Bellman-ford O(nm)，动态规划思想
SPFA 一般：O(m)，最坏O(nm)
（2）多源汇最短路：任意两点最短路径被称为多源最短路径，即给定任意两个点，一个出发点，一个到达点，求这两个点的之间的最短路径，就是任意两点最短路径问题：Floyd算法 O(n^3)
题单
743. 网络延迟时间 - 力扣（LeetCode）
787. K 站中转内最便宜的航班 - 力扣（LeetCode）
1928. 规定时间内到达终点的最小花费 - 力扣（LeetCode）