如何用 FLOYD 算法搜出最短路径。
在上一篇论文中我们介绍了比较了 FLOYD 算法和 DIJISTRA 算法在该项目中的优劣点，在
这篇小论文中我们将讨论如何有 FLOYD 算法把最短路径搜索出来。
一：FLOYD 算法是如何实现搜索最短路径的：
FLOYD 算法又称插点法，它的基本过程如下：
首先，把图用邻接距阵 G 表示出来；如果从 Vi 到 Vj 有路可达，则 G（i,j）=d,d 表示该路
长度，否则 G（i,j）=inf, 最后图可以用如下图来表示。
G =
0 2 3 Inf Inf 9
1 0 4 Inf 4 Inf
1 1 0 Inf 10 Inf
10 Inf 9 0 Inf Inf
7 Inf 2 10 0 4
1 9 8 4 Inf 0
为了搜出最短路径我们还需要一个距阵用来记录所插入点的信息。这个距阵的 D，D（i,j）
表示从 V（i）到 V（j）需要经过的点，初始化 D（i,j）=j
D =
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
评论0