故最短路为A→1→2→4→6→B,最短路长为6 最短路问题可以直接应用于解决生产实际的许多问题,诸如各种管道铺设、线路安排、厂区布 局、设备更新、选址等 (I1)、最短网络。 亦称最小树。一个实际背景是:在若干城市间架设电话线,如何架设使总长最短? 先讲讲什么是树?对于图中的任二顶点V和V,如果从一个顶点出发沿着若干边或弧(有方 向的边叫做弧),可以达到另一顶点,则称所顺次经过的边和顶点为连接V1和V的链。如果所连接 的顶点重合,即V:=V,则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链,则称 为连通图,而连通且无圈的图叫做树 对于含圈的连通圈,去掉每个圈的一条边,便可生成一个树,去掉的边不同生成的树也不一样, 其中边权和最小的,叫做最小生成树。 求最短网络,首先容易想到的是求最小生成树,目前的方法有所谓破圈法(即任取一个圈,每 次去掉其中最长的一条边,直到无圈为止),顶点扩充法(即任取一顶点,考察以此顶点为一端点的 所有的边,取其中最短边的另一顶点为扩充顶点,依次类推,但要注意新扩充的边与已选好的边不 能构成圈,直到所有顶点均被扩充为止)等,计算量是O(n)。 继之想到在原基础上增加一些新点和连线,扩大成一个新的网络,要求在此新网络上找出一个 子网络,它是连通的,包含原图中的点,并且边权和最小,这种网络称为斯坦纳最小树(树中新增 加的点叫斯坦纳点,简称斯点),它的边权和显然小于最小树的,现已证明 任一斯点均为夹角为120的三线段交点。 、n顶点的图形最多含(n-2)个斯点 三个顶点的斯坦纳最小树很容易找出 以AC为边作正△ACD,连BD交△ACD的外接圆于S,则S即为斯点(见图3)8 1 6 5 3 2 A 4 1 3 1 1 2 2 2 1 5 3 2 B 0 6 5 6 3 3 2 1 故最短路为 A B → → → → → 1 2 4 6 ，最短路长为 6。 最短路问题可以直接应用于解决生产实际的许多问题，诸如各种管道铺设、线路安排、厂区布 局、设备更新、选址等。 （II）、最短网络。 亦称最小树。一个实际背景是：在若干城市间架设电话线，如何架设使总长最短？ 先讲讲什么是树？对于图中的任二顶点 Vi 和 Vj，如果从一个顶点出发沿着若干边或弧（有方 向的边叫做弧），可以达到另一顶点，则称所顺次经过的边和顶点为连接 Vi 和 Vj 的链。如果所连接 的顶点重合，即 Vi ＝Vj，则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链，则称 为连通图，而连通且无圈的图叫做树。 对于含圈的连通圈，去掉每个圈的一条边，便可生成一个树，去掉的边不同生成的树也不一样， 其中边权和最小的，叫做最小生成树。 求最短网络，首先容易想到的是求最小生成树，目前的方法有所谓破圈法（即任取一个圈，每 次去掉其中最长的一条边，直到无圈为止），顶点扩充法（即任取一顶点，考察以此顶点为一端点的 所有的边，取其中最短边的另一顶点为扩充顶点，依次类推，但要注意新扩充的边与已选好的边不 能构成圈，直到所有顶点均被扩充为止）等，计算量是 2 O n( ) 。 继之想到在原基础上增加一些新点和连线，扩大成一个新的网络，要求在此新网络上找出一个 子网络，它是连通的，包含原图中的点，并且边权和最小，这种网络称为斯坦纳最小树（树中新增 加的点叫斯坦纳点，简称斯点），它的边权和显然小于最小树的，现已证明： 一、任一斯点均为夹角为 120o 的三线段交点。 二、n 顶点的图形最多含（n－2）个斯点。 三个顶点的斯坦纳最小树很容易找出： 以 AC 为边作正△ACD，连 BD 交△ACD 的外接圆于 S，则 S 即为斯点（见图 3） 1 2 B C A D S