先谈最短路问题归纳：
1.单源最短路
允许有负权环的最短路：
小规模：用Floyd算法（邻接矩阵存储）
大规模：用SPFA算法（链式前向星or邻接表）
不允许有负权环的最短路：
Dijkstra算法（链式前向星or邻接表）
2.多源最短路
只能用Floyd算法（邻接矩阵）
一、详解Floyd算法：
Floyd算法是基于动态规划的算法，它定义了一个状态：
定义：Floyd[i][j] 表示从 i 到 j 的最短路径，这里分两种情况讨论：
第一种情况：从 i 到 j 会经过点 k；
第二种情况：从 i 到 j 不会经过点 k；
很明显，如果不经过点 k，那么就是能够从 i 到 j 直达！
此时：Floyd[i][j] = Floyd[i][j];
如果要经过点 k，那么就要枚举 k，因为每个点 k都是可以经过的（假想）
此时：Floyd[i][j] = Floyd[i][k] + Floyd[k][j];
所以这个时候，我们的动态转移方程就出来了：Floyd[i][j] = min(Floyd[i][j], Floyd[i][k] + Floyd[k][j]);
二、核心代码与模板：
void F(int n){
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
if(inf != Floyd[i][k])// 一个小优化！
for(int j = 1;j <= n;j++)
if(Floyd[i][j] < Floyd[i][k] + Floyd[k][j])
Floyd = Floyd[i][k] + Floyd[k][j];
}
这个代码，我做了一个小优化，能够让它的复杂度从只能承受（n <= 200）到（n <= 500）不成问题！然后需要注意的是，最好不要使用算法库函数：min()因为调用它比较耗时，直接if()比较就好了。
三、模板问题
HDUOJ 2544 最短路径
这是一个很简单的模板题，意思就是求从位置 1到位置 n的最短路径，这是一个单源最短路，但是我们为了作为模板，就那它开刀了（ps：还不是太难的我做不出）
#include <cstdio>
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int Floyd[maxn][maxn], n, m;
int F(){
int begin = 1;
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
if(inf != Floyd[i][k])
for(int j = 1;j <= n;j++)
if(Floyd[i][j] > Floyd[i][k] + Floyd[k][j])
Floyd[i][j] = Floyd[i][k] + Floyd[k][j];
return Floyd[begin][n];
}
int main(){
while(~scanf("%d %d",&n,&m) && 0 != n + m){
int u, v, w;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
Floyd[i][j] = inf;// 先设每两个点之间的距离是无穷大
for(int i = 1;i <= m;i++){
scanf("%d %d %d",&u,&v,&w);
Floyd[u][v] = Floyd[v][u] = w;// 有权图的邻接矩阵值存储的是权重
}
printf("%d\n",F());
}
return 0;
}
四、拓展应用：有向图的传递闭包问题
什么是传递闭包？
先来分析一下：
有向图的邻接矩阵的含义是：如果点a到b能够直达，那么邻接矩阵的arr[a][b] = 1，否则就是为0！
而传递闭包的含义呢？即便是a不能直达b，但是它兜个小圈子，a先到c，c再到d，然后d再到b，那么我们也称a是能够到达b的，此时传递闭包的矩阵arr’[a][b] = 1！
那为什么Floyd算法可以处理有向图的传递闭包问题呢？？
还记得我们Floyd算法有一个非常核心的状态转移方程吗？？
回顾：Floyd[i][j] = min(Floyd[i][j], Floyd[i][k] + Floyd[k][j]);它的含义我们还可以怎么理解？？我们是否可以这样，把min()换成逻辑 || ，然后把 + 换成逻辑 && ？这样的话，我们是不是可以这样认为：i 到 j 如果能够到达，要么i 到 j 有直连路径（即邻接矩阵），要么i，能够通过一些桥梁（k = 1, 2, 3 … n）然后到达 j ？那么你想想，这个桥梁是不是中间不能断开？所以这是与运算，而这两种情况是不是取其一种就好了？所以又要或运算！现在大家懂为何要用Floyd算法处理传递闭包了吧？？Floyd算法真是天生就方便处理这个问题啊！
练习1：HDUOJ 1704 rank
这个题的大意就是，如果能够通过这个有向图，我们能够知道俩人的胜负关系，那就ok，否则就要ans++，胜负关系具有传递性！！所以就是要做传递闭包！
细节处理：
1.传递闭包问题，我们先初始化矩阵为0，如果有直连关系，就赋值为1，然后用Floyd算法，得出全部的可达关系矩阵！！
2.注意这里我们的可达与否用的是位运算和0/1判别
3.如果俩哥们胜负不分，条件是，A既没有搞赢B，同时B也没有搞赢A，因为他们只能打一场比赛，只要他俩打了，胜负就分出来了！
#include <cstdio>
const int maxn = 505;
int Floyd[maxn][maxn], t, n, m;
void F(){
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
if(0 != Floyd[i][k])
for(int j = 1;j <= n;j++)
Floyd[i][j] = Floyd[i][j] || (Floyd[i][k] && Floyd[k][j]);
}
int main(){
scanf("%d",&t);
while(t--){
int ans = 0, u, v;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
Floyd[i][j] = 0;
for(int i = 0;i < m;i++){
scanf("%d %d",&u,&v);
Floyd[u][v] = 1;// 这是一个有向图
}
F();
for(int i = 1;i <= n;i++)
for(int j = i + 1;j <= n;j++)
if(!(Floyd[i][j] || Floyd[j][i]))// 因为两个人只会打一场，所以要是对方有一条路径到你这
ans++;
printf("%d\n",ans);
}
return 0;
}