算法其实都差不多了，更重要的是对算法本身的理解，而不是根据题目去熟悉算法
floyd代码极其简短，只有几行：
for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) { if(i==j||j==k||k==i)continue; f[j][k]=min(f[j][i]+f[i][k],f[j][k]); } 但这是不是说明代码短，可以记住，就可以不动脑子直接用？如果直接用，而不去了解它的原理、精妙之处，那你就只学会了求最短路，而舍弃了一种思维方式，，况且，它还有很多变种、、
板子选手的生存环境越来越恶劣、
所以这看似比模拟还要短的代码里，有远比代码量有多得多的智慧
首先，图的最短路径问题具有递推的性质：
一条最短路径的子路径也是一条最短路径
因为从搜索的角度出发，它实际上是一种合并的过程：
对于每两对点，显然最短路径是唯一的（等价考虑为一种），所以，对于一条边，它只会从一个原点走一次。
显然，我们需要从若干条搜索的路径中选出一条。
对于从起点到达的一个点，它之后的选择是确定的，所以，我们需要取从起点到该点的最短路径
然后结合递推的思想，我们就可以自己构造最短路径的求法：
1、每次都对每一个节点的上一步取最小值，一直取顶点个数次，每进行一次，就会得到每一层的答案 （bellman-ford）
2、从起点分层，每一层找到一个更小的就从那一层更新这一条路，这是利用了搜索+更新的方法，节省了后面搜索的时间（dijkstra）
3、如果我们已经知道这个点之后会被更新，那我们就不用再一次更新这个点了（spfa）
所以如果我们能够发现、判断一些特点，算法是可以自己想出的、
所以求最短路，实际上用了最优子结构、分层、松弛、合并等经典思想，提升对这些思想的理解是可以延伸到很多难题的。
比如，
一、让你求一个最长路（不含环）： 1、最长路径唯一 2、最优子结构 所以直接取最大值即可
二、让你判断/求一个负权环： 1、负权环最短路径是负无穷，所以，如果取最优子结构，则永远取不完。
所以：不含环的最短路一定是一条，而含环的最短路一定有环，，所以再求最短路时，记录前继，更新时判断是否是当前最短路的前继即可，，判断的话只需记录更新次数
三、让你求次短路： 次短路一定是比最短路差一个弯，所以我们只需更新两个值即可
四、让你求经过k条边的最短路： 每一次更新都是 被更新点的路径=上一个点+1 所以我们只需再开一个数组记录经过1~k条边的最短路即可
五、删掉一条边，使最短路尽量大。 首先，要删除的边一定在最短路上，所以容易想到每次枚举删一条边，跑最短路，但这样做是v^2e
所以可以：因为我们只删一条边，所以可以记录次短路，从起点到终点再跑一次 然后枚举每一条最短路边
当然这些算法都比较直观，floyd可能会比较难理解
对于最短路问题，可以这样想：每一次更新，都是通过另一条路径到达了相同的地方
所以：
可以算出每个点走一次的最短路，来更新走两次的最短路，在更新走3~4次的最短路
化成一条链，就是经典的区间dp模型：
但floyd有很大的不同，它第一步只能更新过这个点的路径，但并不能保证它最短，相邻两个点的最短路有可能是最后一次循环才确定的
所以，它的阶段就是只枚举一遍中间点，合并所有过这个点的路径，即找出所有点对的经过这个点的最短距离
网上有一种理解：
主要思想就是先找简化版的模型，然后再往外扩，看原来的方法是否可行，如果不可行是哪些地方不可行。
如这三重循环，实际上有两种作用：1、合并 2、更新
合并是指将两条路合成一条路， 即dis【i，j】=dis【i，k】+dis【k，j】 ，dis【i，j】之前是inf，作用是联通两个图；
更新是指通过另一条路更近 即dis【i，j】=dis【i，k】+dis【k，j】 ，dis【i，j】之前有一条路，但不如ikj更优
这样更新每个中间点，其相邻的点也都被连接，所以在跑完所有点后，所有的路径都会被便历到，
所以，当我们得到一条路径时，它可能会被另一条路径更新，并且我们可以放心的走更小路径（最优子结构）
所以对于floyd便历到的取值情况，我们只需选择较小的，这样一定是正确的（代表这两条路径都试过，不会有遗漏）
所以，它就是一个包含枚举思想的合并过程，这种枚举+最优合并的思想非常常见。
还有一个顺序问题：作为中间点的循环必须在最外层
因为如果把它放在里面，那就相当于对每两个点都扫一遍中间点，而每个点对之间只会被算一次
放在外层是为了保证每一次都能连通至少两个点，而放在内层则有可能发生两个点无论如何也更新不到的情况
所以只能放在最外层
可以看出，对于求解最短路的算法中，都牢牢抓住了一个性质——最优子结构 所以，这些算法都是基于dp的算法
对于一个问题，如果有一个比较巧妙的性质或结论，那这个题就是所谓的难题，所谓的不会做只是没有充分利用题目信息
对于性质的挖掘需要丰富自己的思维角度，从而形成一种直觉 或 通过进行简化、模拟，尝试找出重复与多余
所以解这些题需要自己的思考，通过思考中的点滴来形成有效的积累 ， 有意识 地培养分析题目特点的能力、 善于变化，才能以不变胜万变。
