运筹学基础及应用-63

运筹学新疆农业大学数理学院主讲黄华第六章图与网络分析§6.3最短路问题1、最短路问题从已知的网络图中找出两点之间距离最短（即权和最小）的路。2、相关记号（1）dij表示图中两个相邻点i和j之间的距离（即权）。易见dii=0；约定：当i和j不相邻时，dij=∞；（2）Lij表示图中点i和j之间的最短距离（即最小权和）。易见Lii=0；

即在已知的网络图中，从给定点s出发，要到达目的地t。问：选择怎样的行走路线，可使总行程最短？3、狄克斯屈拉（Dijkstra）标号算法（1）适用范围用于求某两个点之间的最短距离。（2）原理

最短路上任何片段是最短路。v1v2v3v4v5（3）思想按离出发点s的距离由近至远逐步标出最短距离Lsi以及最佳行进路线。SABCDET252414317557例1求图中S到T的最短路及最短距离。（4）步骤

在网络图中求s到t的最短路。第一步从s出发，将Lss=0标记在s旁边的方框内（表示点s已标记）；第二步找出与s相邻且距离最小的点，设为r，计算Lsr=Lss+dsr，并将结果标记在r旁边的方框内（表示点r已标记），同时标记边sr；第三步从已标记的点出发，找出这些点的所有未标记邻点，分别计算已标记点的方框数与其邻点的距离之和，利用“叠加最小”的原则确定下一个被标记点，设为p，并将最小的和标记在p旁边的方框内（表示点p已标记）,同时标记相应边；第四步重复第三步，直到t得到标记为止。SABCDET25241431755702447891413594最短路：SABEDT；最短距离：LST=13例1求图中S到T的最短路及最短距离。V1V2V3V4V5V6V752276742136例2求图中v1到v7的最短路。05277610练习：用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：思考求图中任意两点之间的最短距离。V1V2V3V4V6V752276742136V54、矩阵算法

求任意两点间最短距离的方法注意：D(0)是一个对称矩阵，且对角线上的元素全是0.D（0）=v1v2v3v4v5v6v7V1052∞∞∞∞V250∞27∞∞V32∞07∞4∞V4∞27062∞V5∞7∞6013V6∞∞42106v7∞∞∞∞360V1V2V3V4V6V752276742136V5其中dij（1）=min{dir（0）+drj（0）}⑵构造任意两点间直接到达、或者最多经过1个中间点到达的最短距离矩阵D（1）=dij（1）；即dij(1)为D(0)中第i行和第j行对应元素之和的最小值D（1）=v1v2v3v4v5v6v7V10527126∞V250727410V327065410V47260328V512753013V66442104v7∞10108340其中dij（2）=min{dir（1）+drj（1）}⑶构造任意两点间最多可经过3个中间点到达的最短距离矩阵D（2）=dij（2）；即dij(2)为D(1)中第i行和第j行对应元素之和的最小值D（2）=v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340说明：一般的对于D（k）=dij（k），其中dij（k）=min{dir（k-1）+drj（k-1）}，(k=0,1,2,3,…)最多可经过2k-1个中间点收敛条件：当D（k+1）=D（k）时，计算结束；设网络图有p个点，即最多有p-2个中间点，则2k-1-1<p-22k-1

k-1<log2(p-1)k∴k<log2(p-1)+1，即计算到k=lg(p-1)/lg2+1时，计算结束。注意狄克斯屈拉算法矩阵算法优点既可以求两点之间的最短距离，又可以确定最短路求任意两点之间的最短距离缺点求某两点之间的最短距离不能确定相应两点之间的最短路例3下图中v1—v7表示7个村子，需要联合建立一所小学，已知各村小学生的人数分别为v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。问：学校应建在哪一个村子，可使学生总行程最少？V1V2V3V4V6V752276742136V5v1v2v3v4v5v6v7V105277610V25072548V32706548V47260326V57553013V66442104v710886340解：用矩阵算法得到任意两个村子之间的最短距离如下：

先将每一行的元素乘以该村子的学生人数，得到小学建在相应村子时，该村学生上学时单程所走的路程。再将每一列的元素累加，得到小学建在相应村子时，七个村子的学生上学时单程所走的总路程。小学建在下列村子时，七个村子的学生上学时单程所走的路程v1v2v3v4v5v6v7015060210210180300200028080200160320501750150125100