最短路的Floyd算法4.3.3最短路的Floyd算法FLOYD算法以上介绍的算法用来求源点至各点的最短路。在有些问题中,我们需要知道节点两两之间的最短路,比如选址问题。这类问题可以用DIJKSTRA算法,依次改变源点来求解,但计算比较繁琐。现在介绍一种直接计算任意两节点之间最短路的方法――Floyd算法,该算法由Floyd于1962年提出。4.3.3最短路的Floyd算法Floyd算法是权矩阵迭代算法,记网络的权矩阵为其中4.3.3最短路的Floyd算法算法基本步骤为:(2)计算其中,(3)重复(2),直到此时即为节点i到点j的最短路的距离。(1)令4.3.3最短路的Floyd算法例4.3.4用Floyd算法计算图4-21中任意两节点间的最短路。4.3.3最短路的Floyd算法解:写出图4-21的权矩阵D,并令4.3.3最短路的Floyd算法4.3.3最短路的Floyd算法D1的元素d1ij的意义为i直接到达j及经节点1到达j的两种方式中,最短路线的距离;4.3.3最短路的Floyd算法4.3.3最短路的Floyd算法D2的元素d2ij的意义为i直接到达j及最多经节点1、2到达j的所有方式中,最短路线的距离,这些可能的方式有:i-j,i-1-j,i-2-j,i-1-2-j,i-2-1-j。例如d243=4423表示节点4到节点3在这些方式中取4-2-3为最短路,距离为4。下标‘423’便于在算法结束时确定最短路之用。
全文预览
