先参考此篇博客，了解常规floyd算法是如何求最短路径的，搞懂D和R的意义，再往后看，否则看不懂 https://blog.csdn.net/kabuto_hui/article/details/82886826

Dijkstra算法是解决正权单源点最短路径问题的公认的最好算法，它得到的是最短路径树。但是实际生活中，常常存在不止一条最短路径，我们需要把这些最短路径全部找出来，这是原始dijkstra无法一次做到的。我们也可能需要任意源点到目标点的数据，原始dijkstra只有一个源点，所以也无法一次就得到。总而言之，这是一种复杂度最低，但是局限性大的算法。 改进的Dijkstra算法[1][2]，得到的是最短路径图，可以找出所有最短路径，但仍然无法解决带有负权边的问题。 虽然Floyd算法明显具有更高的时间复杂度（Dijkstra算法时间复杂度:O(n ^2)；Floyd算法时间复杂度:O(n ^3)），但Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法[4]。 本文改进Floyd算法，使其能够只经过一轮迭代，就给出全局任意两点之间所有最短路径或最长路径。 当然，此算法要有解，必须基于以下前提：最短路径要存在，则图上不能有权重之和为负数的环；最长路径要存在，则必须是有向无环图DAG

要求所有最短路径，其实很简单。

不管有几条最短路径，最后获得的距离矩阵D一定是一样的，所以D矩阵迭代更新的部分不需要修改。

原算法之所以只能求得一条最短路径，是因为它只有在 D ( i , K ) + D ( K , j ) < D ( i , j )   D(i,K)+D(K,j) < D(i,j) \, D(i,K)+D(K,j)i,j}=r{i,k};%小于的情况下，对r进行更新替换操作 elseif (d(i,k)+d(k,j)==d(i,j))&&(k~=i)&&(k~=j)&&(d(i,j)~=inf) r{i,j}=[r{i,j},r{i,k}];%等于情况下，对r进行并列放置操作 end end end end r=cellfun(@(x) unique(x),r,'un',0); %R的每个元素中，可能会有重复的数，消去即可 end

注意在等于的情况下，要记得排除k=i或k=j的情况，也要排除d(i,j)=inf 的情况。

因为我们假设图是不存在负权的环路的，所以对角线元素必为0，一旦k=i或k=j，等于号就必定成立了，增添了不必要的元素。

如果不排除d(i,j)=inf，若两个点 i 、j 之间不存在可行路，则等于号对任意k都是必定成立。

∀ K ∈ [ 1 , n ]   ,    D ( i , K ) + D ( K , j ) ≡ D ( i , j ) ≡ i n f \forall K\in [1,n] \ , \ \ D(i,K)+D(K,j) \equiv D(i,j)\equiv inf ∀K∈[1,n] ,  D(i,K)+D(K,j)≡D(i,j)≡inf

会导致把所有k都罗列进来，但这不是我们想要的结果。

示例 1.有向图

距离矩阵 路由矩阵（元胞） 2.无向图

距离矩阵 路由矩阵（元胞） 例如：R(1,10)=[2,3,10] 代表：如果想从1走到10，则下一步走到2，3，10均可。

此算法面对大矩阵（行数大于1000）还是略慢，而且等于的情况越多，就会越慢，但是占用内存不算多，可以接受。 用改进的Dijkstra算法会更快，但是无法解决最长路径问题。

参考文献 [1]王志坚 等. 具有多条最短路径的最短路问题. 哈尔滨工业大学学报. 2010. [2]David B. dijkstraties Modified Dijsktra’s Algorithm to return all paths that tie for shortest. Matlab file exchange. 2012. [3]kabuto_hui. 最短路径-Floyd算法的matlab实现.md. CSDN博客. 2018 [4]《Floyd算法》百度百科 matlab 函数 dijkstraties 求所有最短路径

如何通过路由矩阵列出所有最短路径（最长路径） 且听下回分解——请看（二）