运筹学-路径问题(名校讲义)

《运筹学-路径问题(名校讲义)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十六、二十七讲路径问题§1两点间的最短路问题§2最小生成树问题§3邮路问题及旅行推销员问题§1两点间的最短路问题（1）[例5-4]已知某区的交通运输的公路分布、走向及相应费用示于有向图5-14中。试问：卡车从v1出发经哪条路线到达v7，才能使总行程最短？这就是网络路径问题的典型提法。v70v6v5v2v4v3v176418247653556491385图5-14§1两点间的最短路问题（2）1．求从某点到其它点的最短路算法目前大多采用标号法，即E．W．Dijkstra(狄克斯特拉)算法，现就介绍这种算法的思路和具体步骤。①有关术语设在有向图G=（V，E）中，V=

2、{v1，v2，，vn}，E={e1，e2，，em}，G中每条边e=[vi，vj]都有一个非负实数权值W(e)，则称G为非负赋权图（权可以表示距离、费用和时间等）。设P为图G中u至v的路径，则定义：W(P)=为P的长度§1两点间的最短路问题（3）若P*为G中u至v的路径且满足：W(P)=min[W(P)P为G中u至v的路径]则称P*为u至v的最短路径。②算法思路：设起点为v1，希求出从v1到其它顶点最短路，令d(vj)为v1至vj的最短路长度。则(1)(2)§1两点间的最短路问题（4）对于（2），显然有d(vj)=d(v)+[v至vj的最短路]所以d(v)d(vj)，

3、故在求d(vj)之前，应先求出d(v)。例如，在图5-14中，已求出v1至其它各点的最短距离示如方框内（求解过程将在后面讲述），由此看出：d(v1)

4、2)利用v1得到永久性标号，计算中各点新试探标号。l(v2)=min{l(v1)+W12，l(v2)}=min{0+5，+}=5l(v3)=min{l(v1)+W13，l(v3)}=min{0+4，+}=4同理得：l(v4)=7，l(v5)=+，l(v6)=+，l(v7)=+。取标号最小者为l(v3)=4，于是d(v3)=4，v3A，见表5-5。表5-5l(v)vkv2v3v4v5v6v7254*7+++§1两点间的最短路问题（7）3)v*=v3，用它计算中各点新试探标号。l(v2)=min{l(v3)+W32，l(v2)}=min{4+，5}=5同理，l(

5、v4)=6，l(v5)=12，l(v6)=+，l(v7)=+，继续迭代可得表5-6。最后得出：d(v1)=0，d(v2)=5，d(v3)=4，d(v4)=6，d(v5)=9，d(v6)=8，d(v7)=13当求v1至t点的最短路径时，可从t点向前递推（见教材[例5-15]。§1两点间的最短路问题（8）表5-6l(v)vkv1v2v3v4v5v6v710*++++++254*7+++35*612++46*108+5108*+69*14713*§1两点间的最短路问题（9）寻找最优路径的第二种方法是，把结果表与网络图结合起来，找出哪些永久标号值之差恰等于

6、连接边的权的顶点，然后这些顶点之间连线即为最短路径。求最短路径第三种方法是在表格中找转折点，例如v7最短路径为13，垂直发现14突变，横找带*点是v5，在垂直发现突变为12，。对于非负赋权的无向图，只需将赋权边用两个相反方向的有向边代替即可。对于有负实数权的最短路需加以修改。（此处略）§1两点间的最短路问题（10）2．求任意两点间的最短路算法①福劳德算法（不容许有负回路）。（略）②矩阵相乘法术语（算符）定义及算法思路其中，即dij为A阵中第i行与B阵中第j列对应元素之和取极小值。§1两点间的最短路问题（11）矩阵算法思路是：若一步到达的两点最短路长矩阵为B和已知目前恰走l步到

7、达的两点间最短路长为A。则知，恰走l+1步到达的两点最短路长矩阵必D＝AB。[例5-7]求图5-18的任两点间最短路。[解]1)一步到达矩阵（vii=∞表示无意义，永不走这一步，这与福劳德算法不同）。另外，元素下标表示路径。v62图5-18v5v4v3v2v133723612§1两点间的最短路问题（12）§2最小生成树问题（1）1．问题的提法及现实来源[例5-8]某地区共有10个村庄，村庄之间的公路联系及距离示如教材图5-19。现计划沿公路铺设电话线，使之所有村庄之间可以通话。