[法学]第5章 最短路问题.ppt

本章主要内容： 5.1 基本概念 5.2 最小生成树 （一）基本概念与理论 （二）Kruskal算法（克鲁斯卡尔避圈法、破圈法） （三）丢边法（破圈法） 5.3 最短路问题 （一）Bellman最优化原理 （二）Dijkustra算法（迪克斯特拉双括号法） 5.4 最大流问题 （一）基本概念 （二）双标号算法 § 5.3 最短路问题 def 8：设G =（V, A, W）为一个赋权有向图，Vs为指定发点，Vt为指定收点，其余为中间点，P为G中以Vs到Vt的一条有向路，则称 为路P的长度，若有 则称 为G中从Vs到Vt的最 短路， 为该最短路的长度（此中F为G中 所有从Vs到Vt的全体有向路的集合）。 最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用。 （一）Bellman最优化原理 1 命题1：若P是网络G中从Vs到Vt的一条最小路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。 证明（反证）： 若P1不是从Vs到Vl的最小路，则存在另一条 Vs 到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2) + W(P3)W(P1) + W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更小的一条路，这与P使G中从Vs到Vt的一条最小路矛盾。 2 算法思想： 设G中从Vs到Vt的最短路P：Vs…Vj…Vk…Vt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 ⑵ 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=φ），此时 迭代结束。I称为已标号集合,J称为未标号集合。 ⑶ 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 ⑷ 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，此中 |V|=n （二）Dijkustra算法（迪克斯特拉) ⑸ 以下介绍的是适用于弧权为正值的有向网络中求最短有向路的Dijkstra算法，又称双括号法。事实上该算法亦适用于弧权为负值的有向网络求最短路问题。 例1 求G的最短路， G图形如下。 解：利用上述Dijkstra算法步骤可得表一所示求 解过程，并有最短路P：V6 V4 V3 V1， 最短距离|P|=2+1+5=8。 例2 求如下G之最短路 由表三知 V1 V8 最短路P1：V8 V6 V2 V1 最短路P2：V8 V6 V5 V3 V2 V1 最短路长 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13 （三）通信线路布设问题 例3. 甲、乙两地之间的公路网络如图三，电信公司准备在甲、乙两地沿公路沿线架设一光缆线，问应如何架设此线路方案，以使光缆线路架设总长度最短？ ① 由表四可得 最短路P： V7 V6 V5 V3 V1 最短距离 |P|=10+4+2+6=22 ② 还可得到自V1（甲）到任一中间点之最短路，例如 V1 V4 最短路由表四可知为 P14 V4 V5 V3 V1 |P14|=18 （四