最佳灾情巡视路线.docx

文档介绍：邢台学院
一、实验题目
今年夏天某县遭受水灾,为考察灾情、组织自救,县领导决定,带领有关部
门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各
乡(镇)、村,又回到县政府所在地的路线。
问题:计算由县政府(O 点)到各各乡(镇)、村的最短距离。
图 1 乡镇、村的公路网示意图
二、实验目的
利用迪杰科斯特(dijkstra)算法计算从某一定点到其他各点的最短距离。
三、实验过程
为便于求解,将图1视为一个赋权图T ,图中县政府、各乡(镇)、村均视
为图T 的顶点( 1, .., 53) 19 ~ 53
v i = ,其中v v 对应乡(镇)A ~ R ,
1 ~ 18 v v 对应村1~35, i
各顶点之间的距离为各边上的权。
以下利用迪杰科斯特(dijkstra)算法求解。
对图T 的每个顶点,定义两个标记(l(v), z(v)),其中:
l(v):表示从顶点v (即县政府O )到其他点v 的一条路径的权;
15
z(v):v的父亲点,即路径由 z(v) ® v 。
定义 S 为具有永久标号顶点的集合,根据图T 的各边上的权值,给出邻接矩
阵W :
1
邢台学院
A B L 34 35
W
0 L inf A
æ ö
ç ÷
0 L inf B
ç ÷
= ç M M O M M ÷ M
ç ÷
L 0 34
ç ÷
ç ÷
inf inf L 0 35
è ø
(1) 赋初值:
令
S ={v },l(v ) = 0,"vÎS¢(S的补集) ,令l(v) =W (v ,v) ,
15 15 15
z(v) = v ;
15
(2) 更新l(v)、z(v) :
"vÎS¢ ,l(v) > l(z(v)) +W (z(v),v)(如图2所示),则令l(v) = l(z(v))+W(z(v),v);
(3) 若某 z(v)是使l(v)取最小值的 S¢ 中的顶点,则令 S = S U{z(v)};
(4) 若 S¢ ¹ Æ ,转至步骤(2),否则停止。
v l(v)
v
15
W (z(v),v)
l(z(v))
z(v)
图 2 最短距离计算方法
最后所得的l(v)即为v 到各顶点最短路的权值,由 z(v)逐步向前推至v ,
15 15
即得v 到各顶点的最短路线。
15
四、实验结果
利用matlab软件编写程序(参见附录1),得到O 到各顶点最短距离(如表1)
及各顶点所对应的父亲点(如表2)。
表1 O 到各顶点最短距离
O A B C D E F G H I J K L M N
l
O O P Q R 1 2 3 4 5 6 7 8 9 10
l 0