最短路问题第二节doc.docVIP

第二节 最短路问题及其算法 基本概念： 定义１　在无向图G V,E, 中： 顶点与边相互交错且 i 1,2,…k 的有限非空序列 称为一条从到的通路，记为 （２）边不重复但顶点可重复的通路称为道路，记为 （３）边与顶点均不重复的通路称为路径，记为 通路 道路 路径 定义２　（１）任意两点均有路径的图称为连通图． （２）起点与终点重合的路径称为圈． （３）连通而无圈的图称为树． 定义３　（１）设P u,v 是赋权图G中从u到v的路径， 则称为路径P的权． 在赋权图G中，从顶点u到顶点v的具有最小权的路 ，称为u到v的最短路． 要点：最短路是一条路径，且最短路的任一段也是最短路． 结论： 1 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树． 2 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路． 二、Dijkstra算法：求G中从顶点u0到其余顶点的最短路 设G为赋权有向图或无向图，G边上的权均非负． 对每个顶点，定义两个标记（，），其中: ：表从顶点u0到v的一条路的权． ：v的父亲点，用以确定最短路的路线 算法的过程就是在每一步改进这两个标记，使最终为从顶点u0到v的最短路的权． S：具有永久标号的顶点集 输入: G的带权邻接矩阵 算法步骤： （１）赋初值：令 S＝ , 0 ,令 , （2）更新、： ,若 则令 , 设是使取最小值的中的顶点，则令S S∪ ， （4） 若φ，转2，否则，停止. 用上述算法求出的就是到的最短路的权，从的父亲标记追溯到, 就得到到的最短路的路线. 以上本质为标号法，即给每一个点v定义一个标号l v , 可用手工计算，算法如下： S为标号集， 赋初值：S u0 , l u0 0, 比较大小：设在下列最小值中 d min w u,v +l u : ,, 有一个点. 增加集合S元素个数并标记： 重复 2 3 步，每重复一次，S元素增加一个，重复次数至多与顶点个数相同。 三、每对顶点之间的最短路 1、算法的基本思想 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D 1 、 D 2 、… 、D ，使最后得到的矩阵D 成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径． 2、算法原理—— 求距离矩阵的方法 把带权邻接矩阵W作为距离矩阵的初值，即D 0 W （１）D 1 ，其中 是从vi到vj的只允许以v1作为中间点的路径中最短路的长度． （2），其中 是从vi到vj的只允许以v1 、 v2作为中间点的路径中最短路的长度． … （3） 是从vi到vj的只允许以v1、v2、…、作为中间点的路径中最短路的长度．即是从vi到vj中间可插入任何顶点的路径中最短路的长，因此D v 即是距离矩阵． 3、算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． , rij的含义是从vi到vj的最短路要经过点号为rij的点． 每求得一个D k 时，按下列方式产生相应的新的R k 即当vk被插入任何两点间的最短路径时，被记录在R k 中，依次求时求得，可由R v 来查找任何点对之间最短路的路径． 4、算法原理—— 查找最短路路径的方法 ，则点p1是点i到点j的最短路的中间点. 然后用同样的方法再分头查找．若： 向点i追朔得：, 向点j追朔得： 则由点i到j的最短路的路径为： 5、算法步骤 Floyd算法：求任意两点间的最短路． D i,j ：i到j的距离． R i,j ：i到j之间的插入点． 输入: 带权邻接矩阵w i,j 赋初值： 对所有i,j, d i,j w i,j , r i,j j, k 1 2 更新d i,j , r i,j 对所有i,j，若d i,k +d k,j d i,j ，则d i,j d i,k +d k,j , r i,j k 3 若k v，停止．否则k k+1，转（２）． 6、Matlab编程 function[D,R] floyd a n size a,1 ; D a for i 1:n for j 1:n R i,j j; end end R for k 1:n for i 1:n for j 1:n if D i,k +D k,j D i,j D i,j D i,k +D k,j ; R i,j R i,k ; end end end k D R end 7、例子： 例 求下图中加权图的任意两点间的距离与路径． 解： 说明： 说明： 说明： a [0 9 inf 3 inf;9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0]; [D,R] floyd a 4