弗洛伊德算法图解（【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法）

本文目录

• 【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法
• 弗洛伊德的算法（Floyd’s algorithm ）
• 弗洛伊德算法如何去记录最短路径经过的每一个结点
• 求弗洛伊德算法的详细解释~
• matlab floyd 算法注释
• floyd-warshanll算法是什么啊

【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法

迪杰斯特拉(Dijkstra)算法核心： 按照路径长度递增的次序产生最短路径。

迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路径，而是 一步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。

弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。

弗洛伊德的算法（Floyd’s algorithm ）

假设这个图的weight matrix存在map中，

for (int k=0; k《5; k++)
    for (int i=0; i《5; i++)
        for (int j=0; j《5; j++) if (i != j) {
            if (map)
                map;
        }

处理完之后map存的就是i，j之间的最短路径长度。

简单的说，当执行完一次最外层循环时，map记录的时i，j之间允许使用中间节点｛0, ..., k｝的最短路径。

弗洛伊德算法如何去记录最短路径经过的每一个结点

用path数组的递归实现打印
例如：打印i,j之间的路径
当path的值为k时，分别再去打印i,k和k,j之间的路径
如此递归直至两点间直接有边相连

求弗洛伊德算法的详细解释~

floyd算法思想：1，构建一个邻接矩阵存储任意两点之间的权值如图D0.

2、例如求v1,v4之间的最短路径。先增加v2做中间顶点，D=10;这样就可以了。

3、如不能在离得较远的两点(例v1,v9）直接得到上述可以满足if的中间点，则跟据你书本的代码可以先构建原点到中间点的最短路径，继而就可以求得vi,v9之间的最短路径

matlab floyd 算法注释

A矩阵是邻接矩阵，对角线上为o，其余位置数字表示的是两点之间距离，比如A(1,2)=2,表示从第一个点到第二个点的距离为2.inf是无穷大的意思，这里表示没有直接沟通这两点的路。
n=length(D);设定n为D矩阵的长度。
接下来的两重循环，得到的R矩阵是n*n的矩阵，它每个数据表示的是路径，比如：R(1,3)=1;表示路径为：1-1-3.这里是初始化路径了。
后面的三重循环是floyd算法的关键所在，就是更新路线了。里面的那个判断指的是：
假设有3个点，1
2
3；如果我从1-2-3之间总距离小于1-3的距离，那么我R(1,3)=2；这就是选取更近的路线了。
最后的两个判断是为了不让曾经走过的点再次被遍历。就是不回头的意思了，这个一般都可以忽略了，你照打上去就是了。
不知道这样的解释你是否满意。

floyd-warshanll算法是什么啊

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 　　
　Floyd-Warshall算法的描述如下： 　　for k:=1 to n do for i:=1 to n do for j:=1 to n do if dist; 　　
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 　　
注意单独一条边的路径也不一定是最佳路径。 　　
从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。 　　
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 　　
不可思议的是，只要按排适当，就能得到结果。 　　// dist(i,j) 为从节点i到节点j的最短距离 　　For i←1 to n do 　　For j←1 to n do 　　dist(i,j) = weight(i,j) 　　For k←1 to n do // k为“媒介节点” 　　For i←1 to n do 　　For j←1 to n do 　　if (dist(i,k) + dist(k,j) 《 dist(i,j)) then // 是否是更短的路径？ 　　dist(i,j) = dist(i,k) + dist(k,j) 　　
这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。 　　
这个算法很容易实现，只要几行。 　　
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。 　　
计算每一对顶点间的最短路径（floyd算法） 　　
【例题】设计公共汽车线路(1) 　　现有一张城市地图，图中的顶点为城市，有向边代表两个城市间的连通关系，边上的权即为距离。现在的问题是，为每一对可达的城市间设计一条公共汽车线路，要求线路的长度在所有可能的方案里是最短的。 　　
输入： 　　n (城市数，1≤n≤20) 　　e (有向边数1≤e≤210) 以下e行，每行为边（i,j）和该边的距离wij（1≤i,j≤n） 　　
输出： 　　k行，每行为一条公共汽车线路 　　
分析：本题给出了一个带权有向图，要求计算每一对顶点间的最短路径。这个问题虽然不是图的连通性问题，但是也可以借鉴计算传递闭包的思想：在枚举途径某中间顶点k的任两个顶点对i和j时，将顶点i和顶点j中间加入顶点k后是否连通的判断，改为顶点i途径顶点k至顶点j的路径是否为顶点i至顶点j的最短路径（1≤i，j，k≤n）。 显然三重循环即可计算出任一对顶点间的最短路径。设 n—有向图的结点个数； path—最短路径集合。其中path为vi至vj的最短路上vj的前趋结点序号(1≤i，j≤n)； adj—最短路径矩阵。初始时为有向图的相邻矩阵 　　
我们用类似传递闭包的计算方法反复对adj矩阵进行运算，最后使得adj成为存储每一对顶点间的最短路径的矩阵 　　(1≤i，j≤n) 　　Var 　　adj：array of 0‥n； 　　
计算每一对顶点间最短路径的方法如下： 　　
首先枚举路径上的每一个中间顶点k（1≤k≤n）；然后枚举每一个顶点对（顶点i和顶点j，1≤i，j≤n）。如果i顶点和j顶点间有一条途径顶点k的路径，且该路径长度在目前i顶点和j顶点间的所有条途径中最短，则该方案记入adj adj矩阵的每一个元素初始化为∞； 　　
for i←1 to n do {初始时adj为有向图的相邻矩阵，path存储边信息} 　　for j←1 to n do if wij《》0 then 　　begin 　　adj《》0 {若顶点i可达顶点j，则输出最短路径方案} 　　then begin 　　print（i，j）； 　　writeln； 　　end；{then}