为什么floyd算法可以计算负权值图的最短路径问题
弗洛伊德算法：Dis(i,j) =min(Dis(i,j), Dis(i,k) + Dis(k,j)).
我是这么理解的，Dis(i,k)或Dis(k,j)可以有一条边是负的，只要两者之和不是负的就行，因为两个和为负就会选取到这个组合，但是路径的结果不应该是负的。Dijkstra中S(已求出解)中的每一个点解即最短路径是已求出的,若存在负数路径,可能存在已求出的解不是最优解.
弗洛伊德算法
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}
map[i,j]表示i到j的最短距离
K是穷举i,j的断点
map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路
初中数学最短路径口诀
初中数学中最短路径问题，生动地体现了数学来源于生活，并用数学解决现实生活问题的数学应用性。
两点在直线同侧的最短路径问题
给出一条直线，A、B两点在直线的同侧，要在直线上找到一个点，使这个点到A点和到B点的距离最短。
步骤：
①找到A(或B)关于直线的对称点P
②连接PB(PA)交直线于O，点O就是所要找的点
造桥选址问题
A、B在一条河的两岸，要在河上造一座桥MN，使A到B的路径AMNB最短。
步骤：
①作出河的宽度M′N′
②将M′N′平移，使M′向A点平移，N′向A′点平移，即AA′=M′N′
③连接A′B与河岸b交于N点
④过N点作直线a的垂线，垂足为M 。则MN就是桥的位置.
涉及到两个动点的最短路径问题
给出一个正方形，已知两个定点和两个动点，
要在直线上找到这两个动点，使这四个点所围的四边形周长最小。
步骤：
①找到两个定点关于正方形的边的对称点，
②连接两个对称点，和正方形边的两边有两个交点。
③交点就是动点的位置
例题：
(2015，广西玉林、防城港)如图，已知正方形ABCD边长为3，点E在AB边上且BE=1，点P，Q分别是边BC，CD的动点(均不与顶点重合)，当四边形AEPQ的周长取最小值时，四边形AEPQ的面积是 .
-最短路径
