披坚执锐，所向披靡

今天，在队长的带领下学习了弗洛伊德算法。

一、弗洛伊德（Floyd）算法的概念

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似

二、弗洛伊德（Floyd）算法与迪杰斯特拉算法区别

1.迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径； 弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

2.Floyd算法，则修正了dijkstra算法对于边权为负问题的不足，引入了一个外循环，来遍历每个点，从而查询该点是不是在i和j之间，这样的话，无论边权为负值还是正值，都会被考虑进去。对于邻接矩阵A来说，在k-1次迭代后，A(k-1)[i][j]为所有从顶点i到j且不经过k之后的顶点的最小长度，有可能经过k之前的点。所以在遍历过程中需要比较A[i][j]与A[i][k]+A[k][j]的大小，取小值，表示比较经过k点与不经过k点的路径长度大小。

三、弗洛伊德（Floyd）算法的基本思想

设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij 则vi到vj的最短路径为：min((Lik+Lkj),Lij(直连))，vk的取值为图中所有顶点，可获得vi到vj的最短路径。

四、弗洛伊德（Floyd）算法的步骤

1 .使用二维数组dis储存路径，同时最终状态代表点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！

2 .从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。

3. 而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。

4 .重复上述直到最后插点试探完成。最终dis数组中存放的就是任意两个结点之间的最短距离。

学习应当"披坚执锐，所向披靡"，拥有一往直前的精神。

http://www.dxsbao.com/shijian/472197.html 点此复制本页地址