Floyd算法特点

1、适合求多源最短路径
2、可以求最小环
3、可以有负边权，不能有负环
4、可以求有向图的传递闭包
5、时间复杂度O(n^3)

单源最短路径算法的选择？

Dijkstra + 堆优化？无法处理负边权的问题
SPFA + 堆优化？期望复杂度很优秀，但是复杂度不稳定

基于本书面向的是计算机考研机试，几乎不可能出现故意构造大量数据使得SPFA超时的情况发生，就如同不可能在机试中故意构造数据使得sort函数的复杂度退化到O(n^2)一样。

当然，也为了防止本书爆红之后被出题老师故意针对，后面我们也附上Dijkstra的通用算法模板以备不时之需。

最短路
题目描述：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
输入描述：
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
输出描述：
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
输入样例#:
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
输出样例#:
3
2
题目来源：
DreamJudge 1565

题目解析：最短路径的模板题，直接使用最短路径模板算法即可。

参考代码（通用模板）

/* 
spfa + vector 
SPFA可以有负边权、可以用一点个入队是否超过N次判断是否存在负环 
*/  
#include <bits/stdc++.h>  
using namespace std;  
  
#define INF 0x3f3f3f3f  
const int maxn = 105;  
int n, m;  
  
struct Edge{  
    int u, v, w;  
    Edge(int u, int v, int w):u(u),v(v),w(w) {}  
};  
  
vector<Edge> edges;  
vector<int> G[maxn];  
int dist[maxn]; // 存放起点到i点的最短距离  
int vis[maxn]; // 标记是否访问过  
int p[maxn]; // 存放路径  
  
void spfa(int s) {  
    queue<int> q;  // 如果这个spfa超时的时候可以把队列改为和dijkstra一样的优先队列
    for (int i = 0; i <= n; i++) dist[i] = INF;  
    dist[s] = 0;  
   ...

练习题目

DreamJudge 1344 最短路径问题
DreamJudge 1286 最短路径
DreamJudge 1224 I Wanna Go Home