比较：
| Floyed | Dijkstra(优先队列优化) | SPFA(优先队列优化) | |
| 时间复杂度 | o(n^3) | o(n+m)(logm) | o(km) |
| 基本思想 | 动态规划 | 贪心 | 贪心 |
| 适用范围 | 无负环图 | 无负权图 | 无负环图 |
| 多源最短路 | 不含负权图的低复杂度解 | 含负权边时的单源最短路求解 |
1.Floyed算法
变量声明：
n，N 点的数量
m， M 边的数量
G[ x ][ y ] 图，表示从 x 点到 y 点的边的权值
dis[ i ][ j ] 路径，表示当前情况下 i 点到 j 点的最短路径长度
算法简洁描述：
通过不断选取中间点来更新从点 i 到点 j 的最短路径
更新方式：
将现有的点 i 到 j 的最短距离 与 已知点 i 到中间点 k 的最小距离 + k 到 j 的路径距离 进行比较
公式表述：
dis[ i ][ j ] = min( dis[ i ][ j ] , dis[ i ][ k ] + G[ k ][ j ] )
循环次序：
for temp in spot:for start in spot:for end in spot:基本实现：
目标：
读入一个含有n条边的无负环无向图，求出图中任意两点之间的最短路径
代码：
#include <bits/stdc++.h>
using namespace std;
//n->点数 m->边数
#define N 1000
#define M 2000
int n, m;
//邻接矩阵图数组
int G[N+1][N+1];
//最短路数组
int dis[N+1][N+1];
//算法内容
void Floyed()
{for(int k = 1; k <= n; k++){ //中间点 for(int i = 1; i <= n; i++){ //起始点 if(i == k) continue;for(int j = 1; j <= n; j++){ //末尾点 if(i == j) continue;dis[i][j] = min(dis[i][j], dis[i][k] + G[k][j]); }}}
}int main(void)
{memset(dis, 0x3f, sizeof(dis));scanf("%d%d", &n, &m);//读入无负环无向图 for(int i = 1; i <= m; i++){int x, y, v;scanf("%d%d%d", &x, &y, &v);G[x][y] = G[y][x] = v;}Floyed();return 0;
}2.Dijkstra算法
变量声明：
n, N 图的点
m, M 图的边start 起始点
INF 无穷大
链式前向星edge x 点下标, v 边权值, next 连接点
vis[ i ] 标记从起始点到点 i 的最短路径是否已经更新
dis[ i ] 表示从起始点到点 i 的最短路径值
结构体 ty 收纳点信息，包括点下标 x 和最短路径值 dis
priority_queue<ty>q; 边权升序排列的优先队列
算法简洁描述：
以既定起点的最短路径值为 0 开始，不断地从当前已确定最短路径的点中选取dis值最小的点，用选取点去更新所有相邻点的最短路径
过程描述：
1.更新起始点 dis 为 0，将起始点的信息(下标 和 dis值) 放进优先队列
2.从优先队列中取出一个未用于更新且 dis 值最小的点信息，然后将该点信息丢出队列
3.用取出的点去更新邻近点的 dis 值，并将新更新的点的信息放进优先队列
4.重复2、3操作，直到优先队列元素为空
其实如果利用优先队列优化，而且每个队列元素拿出来用完就丢掉，就不需要判断取出的点是否曾用于更新，这里为了突出这个先决条件，特意声明
简单实例模拟(变量意义看上述)：
现在求从点 1 到各点的最短路径值：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||||||||
| dis[1] | vis[1] | dis[2] | vis[2] | dis[3] | vis[3] | dis[4] | vis[4] | dis[5] | vis[5] | dis[6] | vis[6] | dis[7] | vis[7] | dis[8] | vis[8] | |
| 初始化更新 | 起点的dis值为0，其余dis值为INF，起点最短路径已确定，vis为true | |||||||||||||||
| 0 | T | INF | F | INF | F | INF | F | INF | F | INF | F | INF | F | INF | F | |
| 第一次更新 | 与起点邻接的点有3、4、2，更新dis，vis | |||||||||||||||
| 0 | T | 0+6 | T | 0+5 | T | 0+2 | T | INF | F | INF | F | INF | F | INF | F | |
| 第二次更新 | 在已经更新的点中选取dis最小且未用于更新最短路的点4作为新的起点，更新所有能更新的最短路径，这次只有点5可更新 | |||||||||||||||
| 0 | T | 6 | T | 4 | T | 2 | T | 2+4 | T | INF | F | INF | F | INF | F | |
| 第三次更新 | 选取已经更新的点中dis值最小且未用于更新最短路的点3作为起点，更新最短路 | |||||||||||||||
| 0 | T | 6 | T | 4 | T | 2 | T | 6 | T | 4+5 | T | 4+6 | T | INF | F | |
| 第四次更新 | 继续按上述方式选点，出现dis相同的两点，发现选择点2已经不能更新，所以选择点5 | |||||||||||||||
| 0 | T | 6 | T | 4 | T | 2 | T | 6 | T | 9 | T | 10 | T | 6+7 | T | |
与计算机跑出的结果相同：
基本实现：
目标：
读入一个含有 n 个点的无负权无向图，求出图中从起始点 start 到任意点的最短路径
代码：
#include<bits/stdc++.h>
using namespace std;
//边&点
#define N 100000
#define M 200000
int n, m, start;
//链式前向星存图
int cnt = 0, head[M+1];
struct Node{int x, v, next;
}edge[2*N+1];
void addedge(int x, int y, int v)
{edge[++cnt].v = v;edge[cnt].x = y;edge[cnt].next = head[x];head[x] = cnt;
}
//
int dis[N+1];
bool vis[N+1];
struct ty{int dis, x;bool operator < (const ty &a) const{return dis > a.dis;}
}temp;
priority_queue<ty>q;
//Dijkstra算法
void Dijkstra(int st)
{//将初始点信息放进队列dis[st] = 0;temp.dis = 0; temp.x = st;q.push(temp);//while(!q.empty()){//找到当前队列中边权最小点temp = q.top(); q.pop();int x = temp.x;if(vis[x]) continue;vis[x] = true;//利用取出的点更新最短路for(int i = head[x]; i != -1; i = edge[i].next){int node = edge[i].x;//将可更新点更新，并放进队列if(dis[node] > dis[x] + edge[i].v){dis[node] = dis[x] + edge[i].v;ty ne;ne.dis = dis[node]; ne.x = node;q.push(ne);}}}
} int main(void)
{memset(head, -1, sizeof(head));memset(dis, 0x3f, sizeof(dis));memset(vis, false, sizeof(vis));//存图scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){int x, y, v;scanf("%d%d%d", &x, &y, &v);addedge(x, y, v);addedge(y, x, v);} scanf("%d", &start); Dijkstra(start);return 0;
} 3.SPFA算法
变量声明
n, N 图的点
m, M 图的边start 起始点
链式前向星edge x 点下标, v 边权值, next 连接点
vis[ i ] 标记从起始点到点 i 的最短路径是否已经更新
dis[ i ] 表示从起始点到点 i 的最短路径值
queue<int>q; 存放点下标的队列
简洁描述：
SPFA思路和过程都和Dijkstra相似，不同的是SPFA不会去研究被用于更新最短路的点dis值是否是最小的
过程描述：
1.更新起始点 dis 为 0，放进队列
2.从队列中取出一个点
3.用取出的点更新所有与其相邻的点的 dis 。并且，如果当前队列中没有新更新过的点，就将新更新的点放进队列
4.重复2、3操作，直到队列为空
基本实现：
目标:
读入一个含有 n 个点的无负权无向图，求出图中从起始点 start 到任意点的最短路径
代码:
#include<bits/stdc++.h>
using namespace std;
//边&点
#define N 100000
#define M 200000
int n, m, start;
//链式前向星存图
int cnt = 0, head[M+1];
struct Node{int x, v, next;
}edge[2*N+1];
void addedge(int x, int y, int v)
{edge[++cnt].v = v;edge[cnt].x = y;edge[cnt].next = head[x];head[x] = cnt;
}
//
int dis[N+1];
bool vis[N+1];
queue<int>q;
//SPFA
void spfa(int st)
{//起点初始化，放进队列 dis[st] = 0; vis[st] = 1;q.push(st);while(!q.empty()){//拿出队首元素 int x = q.front(); q.pop();vis[x] = false;//更新最短路径值 for(int i = head[x]; i != -1; i = edge[i].next){int ne = edge[i].x;if(dis[ne] > dis[x] + edge[i].v){dis[ne] = dis[x] + edge[i].v;//如果该元素现在不在队列，放进队列 if(!vis[ne]){q.push(ne);vis[ne] = true;}}}}
}
int main(void)
{memset(dis, 0x3f, sizeof(dis));memset(vis, false, sizeof(vis));memset(head, -1, sizeof(head));//存图scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){int x, y, v;scanf("%d%d%d", &x, &y, &v);addedge(x, y, v);addedge(y, x, v);} scanf("%d", &start); spfa(start);//输出计算结果 for(int i = 1; i <= n; i++){printf("dis %d: %2d ", i, dis[i]);if(i %2 == 0) cout <<endl;} return 0;
} 
