ArcGis Chapter02

附录2 用赋值图法求解最短路径问题

13

赋值图或L矩阵提供了另外一种求解最短路径的方法（Taaffe et al, 1996: 272-275）。

以图A2.1所示的网络为例。这个网络代表了俄亥俄州北部地区的高速公路网，结点1为托莱多（Toledo），结点2为克里夫兰（Cleveland），结点3为剑桥（Cambridge），结点4为哥伦布（Columbus），结点5为代顿（Dayton）。我们用一个L1矩阵来表示这个网络，矩阵的每个元素为两结点之间的直接距离（一步直接相连）。如果两个结点之间没有直接的交通联络，则用一个很大的数M表示。对角线上的元素L1(i, i)都为0，因为结点与自身的距离为0.

接下来，我们用矩阵L2代表2步连接。在L1矩阵中那些非M值的元素保持不变，因为二步连接不可能比一步连接（直接连接）还要短。我们只要修改那些M值即可。例如，L1(1, 3) = M需要修改，下面列出了所有可能的“二步”连接：

L1(1, 1) + L1(1, 3) = 0 + M = M ; L1(1, 2) + L1(2, 3) = 116 + 113 = 229 ; L1(1, 3) + L1(3, 3) = M + 0 = M ; L1(1, 4) + L1(4, 3) = M + 76 = M ; L1(1, 5) + L1(5, 3) = 155 + M = M .

元素L2(1, 3)的值为上述连接的最小值，即L1(1, 2) + L1(2, 3) = 229。值得注意到是，它不仅记录了结点1、3之间的最短距离，也记录了二者之间的通行路径（途经结点2）。

类似地，我们可以得到其他元素的值，有L2(1, 4) = L1(1, 5) + L1(5, 4) = 155 + 77 = 232, L2(2, 5) = L1(2, 4) + L1(4, 5) = 142 + 77 = 219, L2(3, 5) = L1(3, 4) + L1(4, 5) = 76 + 77 = 153，等等。矩阵L2的最终结果见图A2.1。

现在，矩阵L2中所有元素都有一个确定的值，所有M都已经被替换，从而我们得到了最短路径问题的解。如果矩阵L2仍然有待定的M值，则我们需要继续进行矩阵运算，直到所有

32

的M值都被确定的数值替换。例如，L3 可以这样计算：

312L(i,j)?min{L(i,k)?L(k,j),?k}

1

4

表 2.1 求解最短路径问题

始末结点 1, 2 1, 3 1, 4 1, 5 路径包含的曲线段 (1, 2) (1, 3) (1, 2), (2, 4) (1, 2), (2, 5) 最短距离 25 55 70 75 15