matlab的floyd算法
Floyd算法，是一种图论算法，用于在加权图中求解最短路径。

它是以发明者之一、
罗伯特·弗洛伊德的名字命名的。

这个算法同样被用于对于任意两点之间的最长路径（所
谓的最短路径问题）进行求解。

算法描述
给定一个带权的有向图G=(V,E)，其权值函数为w，下面我们定义从顶点i到顶点j的路径经过的最大权值为dist(i,j)。

特别地，当i=j时，dist(i,j)=0。

为了方便描述算法，我们用D(k,i,j)表示从顶点i到顶点j且路径中的所有顶点都在集合{1,2,⋯,k}中的所有路径中，最大边权值的最小值。

则从顶点i到顶点j的最短路径的边权值就是 D(n,i,j)，其中n是图中顶点的数量。

算法思想：建立中间顶点集合
算法是通过不断地扩充中间顶点集合S，来求解任意两点之间的最短路径。

具体来说，设S={1, 2, ⋯, k}，其中k是整数。

Floyd算法的基本思想是，依次考察所有可能的中间
顶点x（即所有S中的顶点），对于每个中间顶点x，若从i到x再到j的路径比已知的路径更短，则更新dist(i,j)为更小的值D(k,i,j)。

最终，在S={1, 2, ⋯, n}的情况下，所得到的D(n,i,j)就是顶点i到顶点j之间的最短路径的长度。

Floyd算法的核心是一个三重循环，在每一轮循环中，枚举S中所有的中间顶点x，通过动态规划计算出从i到j的最短路径长度D(k,i,j)。

这一过程可表述为：
for k = 1 to n
for i = 1 to n
for j = 1 to n
if D(k,i)+D(j,k) < D(k,i,j)
D(k,i,j) = D(k,i)+D(j,k)
其中D(0,i,j)即为dist(i,j)，若i和j不连通，则D(0,i,j)=+Inf。

算法实现
function D = Floyd(adjmat)
% adjmat为邻接矩阵
邻接矩阵adjmat的定义为：
- 若两个顶点之间有边相连，则对应位置为该边的边权值；
- 若两个顶点之间没有边相连，则对应位置为0。

Floyd算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)，并且它能够处理带有负权边的图。

由于其实现简单，常被用于ACM/ICPC和OI等比赛中。

除了求解最短路径问题外，Floyd算法还有其他一些应用。

下面我们来探讨一下Floyd算法的相关内容。

1. 求解最长路径
Floyd算法同样适用于求解任意两点之间的最长路径问题。

具体来说，若原图中边的
权值为正，则可通过一些技巧将其转化为负权值，再使用Floyd算法求解最长路径。

将源
点到终点的距离定义为-w(i,j)，则取相反数后就变成了Floyd算法的最短路径问题。

2. 一般加权图
对于一般的加权图（即边权可能存在负数），Dijkstra算法无法正确地求解最短路径问题。

而Floyd算法则可处理带有负权边的图，但是可能存在负环的情况。

负环是指在图
中至少存在一条环路，其所有边的权值之和为负数。

此时，Floyd算法将会陷入无限循环
的状态中，因此对于存在负环的图，Floyd算法并不适用。

3. 矩阵快速幂
在解决一些NP完全问题（如旅行商问题）时，常常需要使用到矩阵乘法。

而Floyd算法恰好可以通过矩阵乘法的思想来求解最短路径问题。

具体地，若将邻接矩阵的元素表示
为边权值，则矩阵的乘法运算可以表示为两条路径的组合。

若对于两条路径P1和P2，其
长度分别为3和4，则P1 P2的长度为P1经过的节点与P2经过的节点所包含的节点的个数，即7。

而Floyd算法的核心循环中，正是利用了这一思想，即通过中间顶点k对路径进行“组合”。

总结
Floyd算法在求解最短路径问题时具有简单易懂、实用高效的特点。

但是对于存在负
环的图，Floyd算法并不适用。

Floyd算法的时间复杂度为O(n^3)，在处理规模较大的图
时可能存在速度较慢的问题。

在某些情况下，可能需要结合其他算法或优化手段来解决最
短路径问题。

除了Floyd算法，还有其他一些经典的最短路径算法，例如Dijkstra算法和Bellman-Ford算法。

下面我们来简单介绍一下这些算法的特点和应用场景。

1. Dijkstra算法
Dijkstra算法是解决单源最短路径问题的一种贪心算法。

它的基本思想是，在图中从源点出发，依次扩展周围未确定最短路径的顶点，并更新到每个顶点的最短路径和距离。

由于Dijkstra算法只考虑已确定的顶点到源点的最短距离，因此在不存在负权边的情况下，Dijkstra算法具有最优子结构和贪心选择性质，能够保证得到正确的最短路径。

2. Bellman-Ford算法
Bellman-Ford算法是一种解决单源最短路径问题的动态规划算法，它可以处理带有负权边的图。

该算法通过遍历所有的边，逐步更新每个顶点的最短距离，直到所有的最短路
径都被计算出来。

由于该算法需要对所有的边进行遍历，因此时间复杂度较高，但是它比Dijkstra算法更具有通用性，可以适用于更复杂的图结构。

3. 应用场景
在实际应用中，我们要根据具体情况选择合适的最短路径算法。

一般来说，在处理大
规模稠密图时，Floyd算法的速度较慢，不适用于实时计算。

此时，可以考虑使用
Dijkstra算法或Bellman-Ford算法。

如果已经确定了图的具体形态，在不存在负权边的
情况下，可以优先选择Dijkstra算法。

除了最短路径问题外，图论算法还具有其他重要的应用，例如最小生成树、最大流问
题等。

在实际应用中，可以根据不同的问题特点选择合适的算法，从而解决实际问题。