最短路问题(共49张课件)优秀.pptxVIP

Chapter8图与网络优化;§8.3最短路问题;如何用最短的线路将三部电话连起来？

此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。;A;最短路问题：

就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。;定义设连通图D=(V,A)，每一弧a=(vi,vj)，有一个非负权

w(a)=wij(wij≥0)

如果P是D中从vs到vt的一条路，称P中所有弧的权之和为路P的权，记为w(P)。;§8.3最短路问题;迪杰斯特拉（1930-2002,荷兰人），早年钻研物理及数学，

转为计算学。1972年获图灵奖（计算机界的诺贝尔奖）。;若P是从vs到vt间的最短路,vi是P中的一个点,则vs到vi的最短路就是从vs沿P到vi的那条路。;从vs出发，给网络中的每个点对应记录一个数(称为这个点vi的标号)，它或者表示从vs到该点vi的最短路的权(称为P标号,此为永久标号)，或者是从vs到该点vi的最短路的权的上界(称为T标号，此为临时标号)，

方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样至多经过p?1步，当终点vt得到Ｐ标号时，就可以求出从vs到各点的最短路。;P(v),T(v)分别表示点v的P标号和T标号，

Si表示第i步时具P标号点的集合。

为了在求出从vs到各点的距离的同时，也求出从vs到各点的最短路，给每个点v以一个λ值。算法终止时，

若λ(v)=m，表示在从vs到v的最短路上，v的前一个点是vm；

若λ(v)=M，表示D中不含从vs到v的路；

若λ(v)=0表示v=vs。;;

令dij表示vi到vj的直接距离(两点之间有边)，若两点之间没有边，则令dij=?，若两点之间是有向边，则dji=?；令dii=0，s表示始点，t表示终点;1.给始点vs以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，。

2.设节点vi为刚得到P标号的点，考虑点vj，其中

，且vj为T标号。对vj的T标号进行如下修改：

3.比较与vi相邻的所有具有T标号的节点，把最小者改为P标号，即：

当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。;§8.3最短路问题;解:(1)首先给v1以P标号，给其余所有点T标号。;§8.3最短路问题;§8.3最短路问题;§8.3最短路问题;§8.3最短路问题;故算法终止，反向追踪得v1到v8最短路为：;§8.3最短路问题;V1

;;解:(1);;§8.3最短路问题;;故算法终止，得反向追踪得v1到v8的最短路为：;;2;;;;;;;;;由此看到，此方法不仅求出了从v1到v8的最短路长，同时也求出了从v1到任意一点的最短路长。将从v1到任一点的最短路权标在图上，即可求出从v1到任一点的最短路线。本例中v1到v8的最短路线是：;v1→v2→v3一定是v1→v3的最短路，

v1→v2→v3一定是v1→v3的最短路，

S={1,2,4},p2=2

若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。

就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.

第二十三页，共49页。

2、Dijkstra算法

7用Dijkstra算法求下图从v1到v6的最短路。

min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1

最短新路径之长N比原来只连三点的最短路径要短。

min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8

第四十七页，共49页。

权值的意义是广泛的。

2、Dijkstra算法

定义设D为有向赋权图，vs与vt是D中两点，在连接vs与vt的所有路中，权最小的路P0称为从vs到vt的最短路。;例8.7用Dijkstra算法求下图从v1到v6的最短路。