最短路径
我们把带有权值的图称为带权图，边的权值可以理解为两点之间的距离，一张图中任意两点间会有不同的路径相连，最短路径就是指连接两点的这些路径中最短的一条。
我们有多种算法可以有效地解决最短路径问题，需要注意的是，边的权值可以为负，当出现负边权时，有些算法不适用。
一、Floyed-Warshall算法
简称Floyed（弗洛伊德）算法，又称插点法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径，该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyed算法的时间复杂度是O(N^3)，适用于出现负边权的情况。
算法描述：
1、初始化：点u、v如果有边相连，则dis[u,v]=w[u,v]。如果不相连则dis[u,v]=maxlongint div 3。
2、for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if dis[i,j]>dis[i,k]+dis[k,j] then dis[i,j]=dis[i,k]+dis[k,j]
3、dis[i,j]即从i到j的最短路径
算法思想：
三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，如果起点i到k的距离加上点k到到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。
初始化时，把不相连的点之间的距离设为一个很大的数maxlongint div 3，不妨可以看作这两点相隔很远很远，如果两者之间有最短路的话，maxlongint div 3就会更新成最短路径的长度；之所以整除3是为了防止判断时的相加运算结果超出长整型的范围。
算法变形
如果是一个没有边权的图，把相连的两点间的距离设为dis[i,j]=true，不相连的两点设为dis[i,j]=false，用
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
dis[i,j]：=dis[i,j] or (dis[i,k] and dis[k,j])
最后如果dis[i,j]为真，则说明两点之间有路径连通
优缺点分析
Floyd算法适用于多源最短路径，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。