顶点的度数设g=ve.ppt

理解:全局最优=局部最优中的最优 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 */81 Dijkstra算法的基本思想 先把V分成两个子集， 一个设为T, T={v?V│v0到v的最短通路的长已经求出}， 另一个是P=V－T。 显然T≠?，因为至少v0?T。 要不断地扩大T，直到z?T。 T P＝V－T v0 z */81 定理 对于任意的x?P，设LT(x)表示从v0仅经过T中的顶点到x的最短通路的长。若不存在这样的通路，置LT(x)=∞。 称LT(x)为 x关于T的指标。令 LT(t1)=min{LT(x) │x?P} 则 LT(t1)是从v0到t1的最短通路的长。 T P＝V－T v0 t1 注：LT(x)即为教材上的l(t) x */81 定理的证明 若存在从v0到t1的通路其长小于LT(t1)，这条路一定包含了P中的顶点（否则， 与LT(t1)最小性矛盾）。 设t2?P，且t2是从v0到t1的其长度小于LT(t1)的通路中遇到的第一个P中的点。 于是有一条从v0到t2仅经过T中的点的通路， 其长度小于LT(t1)， 而由LT(t2)的定义知， LT(t2)LT(t1), 这与假设 LT(t1)=min{LT(x)│x?P}矛盾。 T P＝V－T v0 t1 t2 */81 命题 设T和P已知，已找出t1, 使 LT(t1)=min{ LT(x) │x?P}。 令 T’=T∪ {t1} P’=P－ {t1}， 并设 LT’(x)表示仅经过T’中的点从v0到x的最短通路的长。则有 LT’(x)=min{LT(x), LT(t1)+W({t1,x})} 这里，若图中{t1,x} ?E, 取W({t1,x})=∞。 v0 t1 x t’ v0 t1 x v0 t1 x */81 命题的证明 从v0到x且不含P’中顶点的任何一条最短通路，只有两种可能的情况： 一条既不包含P’中的顶点也不包含t1的通路. 此时，最短通路长仍然为 LT(x) v0 t1 x */81 命题的证明 (2) 一条由v0到t1不包含P中的其它顶点，然后由t1经过{t1,x}到x的通路。 此时，最短通路长为 LT(t1) +W({t1,x}) . v0 t1 x */81 命题证明的说明：还有一种？ 实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 从 v0到t1，再到 T’中某一顶点t’，由t’到x中间不经P’中点。 v0 t1 x t’ */81 Dijkstra算法 设起点是v0，终点是z。具体程序如下： 开始，设 T={v0}，P=V－T，对P中的每一个顶点x,令 LT(x)=W({v0,x})。 设t1是P中关于T有最小指标的顶点, 即 LT(t1)=min{LT(x) │x?P}。 若t1=z，则终止。 否则，设 T’=T∪ {t1}，P’=P－ {t1}。 对于P’中的每一个顶点 ，计算它关于T’的指标： LT’(x)=min{LT(x), LT(t1)+W({t1,x})}。 把T’代为T,把P’代为P,把LT’(x)代为LT(x)， 重复步骤(2)。 */81 例 求图9.9中从a到z的最短通路的长 a c e b d z 1 4 7 1 2 3 2 6 5 T={a,b}