floyd算法【讨论】最短路径弗洛伊德算法的时间复杂度？

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算法是怎样的?

Floyed算法求解所有顶点对之间的最短路径： procedure floyed; begin for I:=1 to n do for j:=1 to n do if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点} for k:=1 to n do {枚举中间结点} for i:=1 to n do for j:=1 to n do if a[i,k]+a[j,k]< a[i,j] then begin a[i,j]:=a[i,k]+a[k,j]; p[I,j]:=p[k,j]; end; end;

Floyd算法与Dijkstra算法的不同

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。

算法过程：1，从任意一条单边路径开始。

所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。

如果是更新它。

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

算法步骤如下： 　　1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值 　　若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 　　若不存在<V0,Vi>，d(V0,Vi)为∝ 　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 　　3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 　　距离值比不加W的路径要短，则修改此距离值 　　重复上述步骤2、3，直到S中包含所有顶点，即S=T为止

【讨论】最短路径弗洛伊德算法的时间复杂度？

那么你的意思是说四个循环全部都执行了的哦？否则就不是O(n4)。

你看最后一个循环是需要判断进入的，也就是说，那个循环在最内层，本身次数就少，加上排除不合法条件，很少能执行到，根据算法思想，那么应该忽略常数级