最佳灾情巡视路线

邢台学院1一、实验题目今年夏天某县遭受水灾，为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。问题：计算由县政府（O点）到各各乡（镇）、村的最短距离。二、实验目的利用迪杰科斯特（dijkstra）算法计算从某一定点到其他各点的最短距离。三、实验过程为便于求解，将图1视为一个赋权图T，图中县政府、各乡（镇）、村均视为图T的顶点(1,..,53)ivi，其中118~vv对应乡（镇）~AR，1953~vv对应村1~35，各顶点之间的距离为各边上的权。以下利用迪杰科斯特（dijkstra）算法求解。对图T的每个顶点，定义两个标记((),())lvzv，其中：()lv：表示从顶点15v（即县政府O）到其他点v的一条路径的权；()zv：v的父亲点，即路径由()zvv。定义S为具有永久标号顶点的集合，根据图T的各边上的权值，给出邻接矩阵W：图1乡镇、村的公路网示意图邢台学院234012.211.5inf12.2017.6inf11.517.608.234infinf8.2035ABABW(1)赋初值：令15{}Sv，15()0lv，()vSS的补集，令15()(,)lvWvv，15()zvv；(2)更新()()lvzv、：vS，()(())((),)lvlzvWzvv（如图2所示），则令()(())((),)lvlzvWzvv；(3)若某()zv是使()lv取最小值的S中的顶点，则令{()}SSzv；(4)若S，转至步骤(2)，否则停止。最后所得的()lv即为15v到各顶点最短路的权值，由()zv逐步向前推至15v，即得15v到各顶点的最短路线。四、实验结果利用matlab软件编写程序（参见附录1），得到O到各顶点最短距离（如表1）及各顶点所对应的父亲点（如表2）。表1O到各顶点最短距离OABCDEFGHIJKLMNl16.311.911.522.241.755.162.777.561.154.343.739.019.831.1OOPQR12345678910l010.128.012.96.09.214.034.917.527.234.549.749.565.9O1112131415161718192021222324l55.967.364.172.769.960.353.552.946.238.339.649.039.044.3O2526272829303132333435l31.820.628.422.220.835.722.130.223.727.836.015v()lvv((),)Wzvv(())lzv()zv图2最短距离计算方法邢台学院3表2各顶点所对应的父亲点结合表2和邻接矩阵W中的数据，利用社会网络分析软件作出从O到各顶点的最短路线示意图，如图3所示。ABCDEFGHIJKLMNOPQRz11O37911121819216O26OO47O123456789101112131415161718zOO2D256EEFEFJ13I17KK1920212223242526272829303132333435zL252523NNMP26PRQR31AA34图3O到各顶点的最短路线示意图