数学建模案例剖析--图与收集方法建模3装备更新与中间选址

《数学建模案例剖析--图与收集方法建模3装备更新与中间选址》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、§3设备更新与中心选址一、指定顶点对之间的最短路径算法对■图G每一条边勺都规定一个正实数q(勺)与Z对应，所得到的图称为赋权图，称q(勺)为边勺的权。边(v,,vj)±的权记成o对赋权图G,V5,teVfG屮的($』)一路称为最短路，如果它的各边的权和是G屮任—•条(£,/)一路中各边权和最小的。找寻(叩)最短路最有效的算法是Dijkstra算法：其主要思路是假定我们已经知道了在图屮与起点s有最短路径的m个顶点以及从s到这些顶点间的最短路径，然后求出第加+1个顶点使之与前加个顶点有相同的属性。其实现方法是比较法。对于每一个未着

2、色的顶点y,考虑所有已着色的顶点兀，从耳通过已着色的顶点到y的不同路径屮选出它们屮的最短路径，从而也就确定了新染色的点和相应的最短路径，不断重复上述过程肓至求得从$至畀的最短路径为止。算法步骤如下：1、最初，所有的边和顶点均未着色，对每一顶点兀指定一个数d。)，表示从s到兀且仅使用己着色顶点作为屮间顶点的最短路径长度。2、令d(5)=0,并对所有兀北$,有d(x)=oo,对顶点s着色并令y=s°3、对于每一个未着色顶点兀，重新定义d⑴如下d(x)=min{j(x),d(y)+a(y,x)}如果对于所有未着色的顶点兀，d(X)=

3、oo,则算法停止，因为此时从S、到任一未着色的顶点都没有路，也就不存在从S至I”的路径。否则找出一个具冇授小的d(x)值的顶点，对其着色并令)'=兀。4、重复步骤3直到顶点/已经着色时为止，算法终止。从$至I"的最短路径已求岀。例：用Dijkdtra算法求下图屮从顶点$至骑的最短路径。33c3d21、对$着色，令d(5)=0,R对其余顶点均有d(x)=-,(兀hs).2、令y=$,对所有兀求解：d(a)=min{d(a),d(s)+a($,d)}=4d(b)=min{〃(Z?),〃($)+d($,b)}=7d(c)=min{d

4、(c),d($)+a($,c)}=3d(d)=min{d(d),d($)+a(s,d)}=8d(/)=min{d(f),d(s、)+8由于d(c)=3最小，再对c着色，并对边($,c)着色。由于f未着色，继续上述步骤。3、令y=c，比较与所有未着色的顶点。d(a)=min{d(a),d(c)+a(c,a)}=4d(b)=min{d@),d(c)+d(c,b)}=7d(d)=min{d(d),d(c)+a(c,d)}=6d(r)=min{d(r),d(c)+a(c,r)}=8由于d(d)=4最小，所以首先对a着色，并对边($卫)

5、着色。由于/耒着色，继续上述步骤。4、令y=a，比较还未着色的顶点。d(b)=min{d@),d(Q)+Q(a,b)}=7d(d)=min{d(d),d(cz)+a(o,d)}=6d(r)=min{d(/),d(a)+a(a,/)}=8由于d(d)=6最小，所以首先对d着色，并对边(c,〃)着色。由于『未着色，继续上述步骤。5、令y=d,继续比较有d(/)=min{d(f),d(d)+d(d」)}=8d@)=min{d(b),d(d)+a(〃,b)}=7对顶点b着色，并对边(s,b)着色。6、令y=b,计算d(0=min{j(

6、td(b)+a(b,Z)}=8最后对顶点f着色和对边(d,r)着色,形成从s到门［勺最短路，最短路径为8,由边(s,c),(c,d),(d,r)组成最短路径。二、所有顶点间最短路径算法一个图中所有顶点间的最短路径算法是一个更具有普遍意义的问题。以卜•介绍Floyd(福劳徳)提出的算法，其具体思路如下：对一个有兀个顶点的图G,将顶点用〃个整数(从1到)进行编号。令硝表示从顶点2•到/的一条只允许前加个顶点作为中间顶点时的最短距离。如果这样的路不存在，则d；=oo0由此定义可知，d》表示从顶点i到丿•的边长度(如果没有这条边存在

7、，则妨=-),显然dJ=()。而碍就是我们所要求解的从i到j的最矩路径距离。算法步骤如下：1、将图中各顶点编号为1,2,…确定矩阵D°,如果顶点i和间冇边相连，d》等于该边长度，否则JJ=oo,而〃》=0。2、对加=1,2,…，M,依次利用递归公式df=min{

8、04加的各元素和相应的最短路径计算如口加的第一•行和第一列元素与相同，对角线上的元索均为0,则需计算其余6个元素如F：d；3=minp；〔+d£,d£}=min{4,7}=4=min{d£+〃$,d学4}=min{5,oo}=5d；2=minpf]+d$,d£}=min{6,