第四节加权连通图上网最短路径问题

第四节加权连通图上网最短路径问题设),(EVG为简单连通图，且给各边赋予非负权值，求G中顶点u到v的最短路径的长度下面介绍解决此问题的Dijkstra(1959)算法先介绍此算法的要求(1)把V分成两个子集S和T.开始时}{uS，SVT，然后不断扩充S，直到Sv.(2)对于T中每一元素x计算)(xt.根据)(xt的值找出T中距u最短的顶点z.(3)把z加入到S中.重复（2），直到Sv.在每次迭代中，若)}}({min)(|{xtxtTxzTx,则u到t的最短路径长度恰为)(zt，在初始阶段}{uS，则Tx，)()(uxwxt.)(uxw表示边ux的权值；若u和x间不存在边，则令)(uxw，在之后的每次迭代中用来更新)}()(),(min{uxwutxt来更新))((Suxt，直到Sv.例1.加权连通图如图所示，求a到各个顶点的最短路径长度11bcdefg1122223131a11111441411111bcdefg11222a111111图G图G1重复次数S)(bti)(cti)(dti)(eti)(fti)(gti开始{a}232∞∞∞1{a,b}3()2()64∞2{a,b,d}3()6463{a,b,d,c}6464{a,b,d,c,f}555{a,b,d,c,f,e}5其中代表的是}3,3min{)}()(),(min{11bcwbtct代表的是}2,2min{)}()(),(min{11bdwbtdt代表的是}4,3min{)}()(),(min{22cdwdtct排序通过比较进行排序的任意算法可以有一棵称为决策树（decisiontree）的(完全)二叉树表示.下图给出排序三个数cba,,的计算机程序的决策树ab?bc?ac?abccabbacbc?cba1111111111111111是是是是是acb11bca否否否否否11ac?高度为h的二叉树至少有h2个叶子给n个数排序由!n种可能，故要找有!n个叶子的二叉树的最小高度是多少22222log2...1log!log2!nhnnnnnhn对于4n有nnnnnnn22222log42log22log!log