给定k,从i到j的路径可以划分为两个集合,一个只包含编号为1,...,k-1的节点作为
中介节点,一个除此之外还允许包含编号为k的节点作为中介节点,后者一定小于等于前者。
因为k号节点只访问一次,所以分成i..k和k..j两段来求,每一段都只包含1,...,k-1的中介
节点。(i,j)的初值是没有中介节点的情形,然后k循环到N就是一个一个比大小穷尽了所有
可能情形,明白了吗?
【 在 ooolinux 的大作中提到: 】
: GUI程序应该可以演示过程,求出每对节点间的最短路径。但它们是不是最终的最短路径,从GUI应该看不出来,除非再运行一次数值没有变化(但也可能是特例偶然的,不是充分的证明)
: --发自 ismth(丝滑版)
--
FROM 116.230.17.*