Question

MATLAB中如何求最短路径

Answer 1

1、最短路问题
两个指定顶点之间的最短路径。
例如，给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。
以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数)(ew—直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点00,vu间的具最小权的轨。这条轨叫做00,vu间的最短路，它的权叫做00,vu间的距离，亦记作),(00vud。
求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距0u从近到远为顺序，依次求得0u到G的各顶点的最短路和距离，直至0v（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令0)(0ul，对0uv，令)(vl，}{00uS，0i。
(ii) 对每个iSv（iiSVS\），用
)}
()(),({minuvwulvli
Su
代替)(vl。计算)}({minvli
Sv，把达到这个最小值的一个顶点记为1iu，令
《计量地理学》（徐建华，高等教育出版社，2005）配套实习指导
140
}{11iiiuSS。
(iii). 若1||Vi，停止；若1||Vi，用1i代替i，转(ii)。
算法结束时，从0u到各顶点v的距离由v的最后一次的标号)(vl给出。在v进入iS之前的标号)(vl叫T标号，v进入iS时的标号)(vl叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，0u至各项点的最短路也在图上标示出来了。
2、选址问题－以中位点选址为例
中位点选址问题的质量判据为：使最佳选址为止所在的定点到网络图中其他顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。