FLOYD算法中的“末前点路径矩阵”表示法

FLOYD 算法是求解网络最短路问题中的一个最重要的算法,该算法在求解过程中以路长矩阵和路径矩阵为工具,通过逐次迭代最终可求得任意点对间的最短路。本文提出的“末前点路径矩阵”表示法就是在每次迭代时用每一点对间真正使用的最末一个前点来表示其路径。这种路径矩阵的表示方法较过去使用的方法更为简单、方便,而且也能迅速和有效地求得任一点对间的具体路径。此法可推广应用于其他需要列出路径矩阵的多种算法中。