运筹学最短路邮递员问题.ppt

狄克斯拉（Dijkstra）算法 最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法—狄克斯拉（Dijkstra）算法，这一算法是1959年首次被提出来的。该算法适用于每条弧的权数ωij ≥0情形。算法的基本思路：从发点vs 出发，有一个假想的流沿网络一切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向继续前进，则最先到达终点vt 的流所走过的路径一定是最短的。为了实现这一想法，对假想流依次到达的点，依次给予p标号，表示vs到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示vs到这些点的最短距离的估计值。具体作法如下： 1°标p（vs）=0，其余点标T（vi）=+∞; 2°由刚刚获得p标号的vi 点出发，改善它的相邻点vj 的T标号,即 新的T（vj）=min{老的T（vj），p（vi）+ ωij } 若T（vj）= p（vi）+ ωij ，则记k（vj ）=vi（前点标记）; 3°找出具有最小T标号的点，将其标号改为p标号。若vt 已获得p标号，则已找到最短路，由k（vt）反向追踪，就可找出vs 到vt 的最短路径，p（vt）就是vs 到vt 的最短距离。否则，转2°。 从一点到任意点的最短路 木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。 表示网络图形的特点 1、与欧氏几何的区别为，图中线的长短并不能表示真实的长度。 2、与地图的区别为两点之间的距离并不真实。 表示网络图形的特点 网络（图论）中两点之间的距离由两点间的边上的权来表示。（可由图中的点1、2与点1、3之间的关系来看）。 求网络上的一点到其它点的最短路 Dijkstra算法 图示 Dinkstra标号法 这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。 在这个问题中我们讨论的是从网络中的点1到其它各点的最短路。 小结 ①从点1出发，因L(1,1)=0，在点1处标记 ②从点1出发，找相邻点r使得边L(1,r)权数（距离）最小，若L(1,r) = L(1,1)+ d(1,r) 将 标于点r处。并将边1r变红。 ③从已标号的点出发，找与这些相邻点最小权数（距离）者，若L(1,p) =Min{L(1,r)+ d(r,p)} ，这里r为已标号者下标，p为未标号下标，则将 标于p处。并把(r,p)边变红。 ④重复上述步骤，直至全部的点都标完。 例2 教育部门打算在某新建城区建一所学校，让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示，学校应建在哪个居民区，才能使大家都方便？（图中距离单位：百米）。 v1 v2 v3 v4 v5 v6 0 0 1 ? 2 ? ? 1 ? 0 4 5 ? ? 2 ? 2 0 5 1+4 ? 1 ? 4 ? 0 6 ? v5 ? ? 2 3 0 ? v6 ? ? 2 ? 2 0 v1 v2 v3 v4 v5 v6 0 0 1 ? 2 ? ? 1 ? 0 4 5 ? ? 2 ? 2 0 5 5 ? 1 ? 4 ? 0 6 ? v5 ? ? 2 3 0 ? v6 ? ? 2 ? 2 0 v1 v2 v3 v4 v5 v6 0 0 1 ? 2 ? ? 1 ? 0 4 5 ? ? 2 ? 2 0 5 5 ? 1 ? 4 ? 0 6 ? 3 ? ? 2 3 0 ? v6 ? ? 2 ? 2