这里要介绍由弗洛伊德(Floyd)提出的另一个算法。这个算法的时间复杂度也是O(n3),但形式上简单些。
弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是：
假设求从顶点vi 到vj 的最短路径。如果从vi 到vi 有弧，则从vi 到vj 存在一条长度为edges[i][j]的路径，该路径不一定是最短路径，尚需进行n 次试探。首先考虑路径（vi, v0,vj）是否存在（即判别弧（vi, v0）和(v0, vj)是否存在）。如果存在，则比较（vi, vj）和（vi,v0, vj）的路径长度取长度较短者为从vi 到vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点v1，也就是说，如果（vi, …, v1）和（v1, …, vj）分别是当前找到的中间顶点的序号不大于0 的最短路径，那么（vi, …, v1, … , vj） 就有可能是从vi 到vj 的中间顶点的序号不大于1 的最短路径。将它和已经得到的从vi 到vj 中间顶点序号不大于0 的最短路径相比较，从中选出中间顶点的序号不大于1 的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推。在一般情况下，若（vi, …, vk）和（vk, …, vj）
按此方法，可以同时求得各对顶点间的最短路径。
现定义一个n 阶方阵序列。
D(-1)，D(0)，D(1)，…，D(k)，D(n-1)