logo资料库

第k条最短路径算法.doc

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.22M 资料格式：doc 举报 版权申诉
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
资料共29页，剩余部分请下载后查看
    双向搜索算法
    第 K 条最短路的算法介绍 1、前言 大家现在已经知道了如何求单源点最短路径问题，但在实际应用中，有时候需要除了需 要知道最短路径外，尚需求解次最短路或第三最短路，即要知道多条最短路，并排出其长度 增加的顺序。如在通信网络中，有时候某条线路中断，则需要找一个替代的方案，这就需要 找到几条最短路以备不时之需。这样一类多条最短路问题即称为 K 最短路问题。 2、二重扫除算法 求解第 K 条最短路主要应用的是二重扫除算法（double-sweep algorithm），有些地方也 叫双向扫除算法。 2.1 概念介绍 在介绍这个具体算法之前，我们要先来看几个概念，这几个概念在后面具体的算法介绍 时需要用到。先看第一个概念，是两类推广运算。  两类运算：推广的求极小值运算与推广的加法运算 令 Rk 表示向量（d1，d2，…，dk）的集合，dij。 2.2 算法思想介绍 下面我们来看一下双重扫除算法。这个算法的思想其实还是比较简单的，就是实现起来 比较复杂，要涉及到两种迭代及矩阵运算，当然还包括前面提及的推广的求极小值运算与推 广的加法运算。 它的思想是：从原始点到顶点 j 的第 K 条最短路是由原始点到顶点 i（i 是 j 的相邻顶点，
    最短路从 i 指向 j）的第 K 条最短路加上 i 到 j 的一段弧。即把与 i 关联的弧作为 K 最短路 的最后一段扫视一遍，无论是前向运算或是后向运算，都需要从 L 或 U 中取出 dij 元素参加 运算，dij 元素在运算中作为 K 最短路的最后一段弧被挑选，并且以前一次运算的向量为基 础，取相应的中间点。 2.3 算法过程 在双重扫除算法过程中，主要反复执行加法和求极小值的运算。 对于每个有向图，我们先对它进行分析，可以用向量 d 0 ij  ( d 0 1 ij , d 0 ij 2 ,  , d 0 ijk ) 表示从 i 到 j 的 k 条不同最短路的长度。而 D0 是以 0 ijd 为元素的矩阵。注意，它的元素是 0 ijd ，这表 示这个矩阵中的每个元素都是一个向量，每个向量表示的是从 i 到 j 的 k 条最短路，即是 k 维向量，如若遇到不足 k 维的，则以∞补全。如图 1，若 k 为 3，则它的 D0 矩阵可以表示为： 0D  ,0( )  ( ) ,  ( ) ,  ( ) ,  , , , ,       ) ,2(  ,0( )  ,2( )  ( , )  , , , , ,5( )  , ) (  ,0( )  ( , )  , , , , , ) (  ,3( )  ,3( )  ,0( )  , , , ,       2 1 5 3 3 4 2 2 3 图 1 其实从这个矩阵中我们可以看到各个顶点间是否有有向边相连，同时还可以知道该有向 边的权值。因为运算中找最短路径，实际上就是计算各条通路的边的权值和再加以比较，从 而得到最小值或次小值。 由 D0 我们可以得到上三角矩阵 U 和下三角矩阵 L 如下： U  L  (   (   (  (  ( ( ( (       , , , , , , , ,         , , , , , , , , ) ) ) ) ) ) ) ) ,2( )  ( , )  ( , )  ( , )  ) ( ,  ) , (  ,2( )  ( , )  , , , , , , , , ,5( )  ( ) ,  ( ) ,  ( , )  ( , ) ( , ) ( , ) ( , )     , , , , , , , ,       , ) (  ,3( )  ,3( )  ( , )  ( , ) ( , ) ( , ) ( , )     , , , , , , , ,       算法的具体思路如下： ⑴ 先设个向量，对原始点到各顶点的最短路长度进行估计。要注意各个值要不小于相 应的最优值。除原始点到其本身的最短路用 0 估计外，其余都可以用∞来估计。即为： d )0( 1  ( d )0( 11 ，，，  d )0( 12 d )0( N1 )  0((   ，， (),  k 个    ，， ), k 个 (, ))    ，， k 个 显然， 0 1d 是个元素值为向量的向量。其中向量 0 ijd 表示从 i 到 j 的 k 条最短的不同路的 长度。 如图 1 中，令 d10＝（（0，∞，∞），（∞，∞，∞），（∞，∞，∞），（∞，∞，∞）） ⑵ 然后根据原来的估计值，可以根据前向和后向扫除计算出新的估计值：
    后向扫除：d1(2r+1)＝d1(2r+1)L＋d1(2r) 前向扫除：d1(2r+2)＝d1(2r+2)U＋d1(2r＋1) （r＝0，1，2，…） 其中矩阵运算中的加法和乘法分别指前面提及的推广的求极小值和推广的加法运算。令 V  ，，，  (  ) ，可将后向扫除公式分解为： r )1  ( d 2( 11 r )1  , d 2( 12 ,  , d 2( 1 N r )1  )  ( d )2( r 11 , d )2( r 12 ,  , d )2( r 1 N )  ( d 2( 11 r )1  , d 2( 12 r )1  ,  , d 2( 1 N r )1     )     V V   V V 0 d V 21  0 d V N  d 0 N 1 2        由上式可见在求 2( )1 rd 1 时， 2( )1 rd 1 本身也参与了运算，但是，观察 L，我们可知 L 的 最 后 一 列 元 素 全 为 V  ，，，  (  ) ， 由 于 VVA   ， 而 VA   A ， 所 以 r d 2( 1 N )1  d )2( r 1 N ；而求 2( Nd 1 )1 r  1  时，只需知道 r )1 2( Nd 1 ，不需知道其它几项；由此一步步往前推， 我们可以将整个 2( )1 rd 1 各个元素的计算式： 完整地计算出来，因此称其为后向扫除。如下，是 2( )1 rd 1 向量中的 即 d 2( 1 N r )1   d )2( r 1 N  ( d 2( 11 r )1  , d 2( 12 r )1  ,  , d 2( 1 N r )1     )     V V  V        d 2( 1 N )1 r  1   d )2( r 1 1 N   ( d 2( 11 r )1  , d 2( 1 N )1 r  1  ,  , d 2( 1 N r )1  )  d )2( r 1 N        V V  0 NN d 1          d )2( r 1 1 N   d 2( 1 N r )1   d 0 NN 1  …… r )1  d 2( 11  d )2( r 11  ( d 2( 11 r )1  , d 2( 12 r )1  ,  , d 2( 1 N r )1     )     V 0 d 21  0 N d 1         d )2( r 11  ( d 2( 12 r )1   d 0 21    d 2( 1 N r )1   d 0 N 1 ) 同理：我们可以将前向扫除的计算公式进行分解，如下： r  )2 ( d 2( 11 r  )2 , d 2( 12 ,  , d 2( 1 N r  )2 )  ( d 2( 11 r )1  r )1  , d 2( 12 ,  , d 2( 1 N r )1  )  ( d 2( 11 r  )2 r  )2 , d 2( 12 ,  , d 2( 1 N r  )2    )       0 0 d dV 12 1 N 0 V d V 22  V V  V        在计算 )2 2( rd 1 时也要用到 )2 2( rd 1 其本身，但根据 U 的特点，我们可以发现先可以计算
    出 )2 2( rd 11 ，然后可以依次计算出 )2 2( rd 12 ， )2 2( rd 13 ，……，这与上面的后向扫除类似，只是 这里我们要先从前面开始计算，因此称其为前向扫除。具体的 )2 2( rd 1 的各个元素的计算式 与上面后向扫除类似，这里就不一一写出了。 如图 1，可计算 d141＝（∞，∞，∞），d131＝（∞，∞，∞）， d121＝（∞，∞，∞），d111＝（0，∞，∞）；（后向） （前向）d112＝（0，∞，∞）， d122＝（∞，∞，∞）+（0，∞，∞）×（2，∞，∞）＝（2，∞，∞） d132＝（∞，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞） d142＝（∞，∞，∞）+（2，∞，∞）×（3，∞，∞） +（5，∞，∞）×（3，∞，∞）＝（5，8，∞）； （后向）d143＝（5，8，∞）， d133＝（5，∞，∞） d123＝（2，∞，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞） d112＝（0，∞，∞）； （前向）d113＝（0，∞，∞）， d123＝（2，7，∞）+（0，∞，∞）×（2，∞，∞）＝（2，7，∞） d133＝（5，∞，∞）+（0，∞，∞）×（5，∞，∞）＝（5，∞，∞） d143＝（5，8，∞）+（2，7，∞）×（3，∞，∞） +（5，∞，∞）×（3，∞，∞）＝（5，8，10）； （后向）d144＝（5，8，10）， d134＝（5，∞，∞） d124＝（2，7，∞）+（5，∞，∞）×（2，∞，∞）＝（2，7，∞） d114＝（0，∞，∞）； 显然，第三第四次迭代后，运算结果相同，从而可得： d1＝（（0，∞，∞），（2，7，∞），（5，∞，∞），（5，8，10）） ⑶ 当 d )( t 1  ( d )( t ，，，  11 )( t 12 d d )( t N1 ) 与 d )1( t   1 ( d  )1( t 11 ，，， d  )1( t 12  d )1( t  N1 ) 的每个分量都 相等时，算法中止。 2.4 路径的确定 K 最短路长度求得以后，我们要确定相应的路径，这时我们可以采用追踪的方法。设需 要知道从源顶点到 i 顶点的第 m 最短路长的路径，我们可以令 miH 为该路的路长，并且令 j 表示与 i 相邻的顶点，则 H mi  H tj  d ji 这里 jid 是弧 ji 的长度， tjH 是对应与顶点 j 的 t 最短路长度，t≤m。
    曾经在网上找了很多关于 PageRank 的论文,基本上都是介绍原理的,没有找到计算过程的具体实现的源代 码,前一阵公司有需要于是写了一个,比较简单(没有反作弊,Blog 链接的处理,黑洞的处理都没有管),就是用 极限编程的思想用最快的速度实现了一个个人感觉计算效率还不错,(没分块,其实前期分块后对后续的计 算过程也是一样的了 P4 3.0,512M),1700 万网页迭代一次需要 25 秒钟的样子. SortMap.dat 是一个链接关系文件,已经按照 DocID(每个网页的唯一编号,64 位整型)进行排序了. 基本上对这样的大文件排序都是进行分割,排序,归并实现的(大家有兴趣的话我下次将排序源代码也贴上 来).如果您手头没有这样的链接数据话 http://www.sogou.com/labs/dl/t-link.html(互联网语料链接 关系库),这个里面可以提取,然后就是排序,然后就是下面的源代码计算,你就能看到传说中的 PageRank 了.Good Luck! PageRank 计算实现原理 PageRank 基本原理 可能有点帮助吧,中文的 PageRank 学习笔记 后面是计算 PageRank 的源代码,希望大家喜欢:(这里贴源代码确实太难看了 ) #include #include #include #include #include #include #include #include #include #include "../FileSort/Sort.h " //一个实现快速排序的文件,后面需要排序的函数都在这个文件中 (64*1024*1024) 8 #define BLOCKSIZE //#define GROUP #define LENGTHOFSINGLE #define OUTDEGREESIZE #pragma pack(1) 8 2048 using namespace std; //实现二分查找功能 template binaryFind(type_key *begin,type_key *end,const type_key &value)
    return end-begin; __int64 size = sizeof(type_key); len = (end-begin); total = (end-begin); low=0; high=total-1; if(begin> =end) //unsigned //long int int int int mid=0; unsigned __int64 while(low <=high) { temp = 0; mid = (low+high)/2; temp = *(begin+mid); if(temp==value) { return mid; } if(temp> value) { high=mid-1; continue; } else { low=mid+1; continue; } } return } total; //完成将 DocID 转换成 Index 的过程,以后每次迭代不用再进行查找,算是中间的辅助函数 unsigned { int BuildIndex(FILE * mapFile) to build index " <
    fread(&total,4,1,countFile); fread(&MaxOutDegree,4,1,countFile); fclose(countFile); cout < < "total is :/t " < 0) if { the MaxOutDegree: " <
    } fcloseall(); delete delete []index; []sons; } cout < < "over total; return } build the index " < =2) file = fopen(argv[1], "rb "); else file = fopen( "F://ren//SortMap.dat ", "rb "); if(file==NULL) cout < < "--------can not open the file-------- " < 0) { //真正实现的计算过程 total the *DocIDIndex = fopen( "DocID.Index ", "rb "); is: " <
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料