硅谷杂志：任意两点间最短路径的新算法研究 |
| 2012-12-16 21:20 作者：孙平 李征宇 王凤英 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
【硅谷网文】据《硅谷》杂志2012年第19期刊文，最短路径问题是图论研究中的一个经典算法问题，Dijkstra算法和Floyd算法是解决任意两点间最短路径的常用办法。从局部最优到整体最优的思想出发，得出求解最短路径的一个新方法，即两点间的最短路径是途经当前最短路径集的复合路径和直达路径的最短者，然后以此方法给出求解任意两点间最短路径的一个新算法，最后简述新算法在针对特定问题时相对于经典算法的优势。
0引言
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两结点之间的最短路径。在实际应用中有着重要意义，特别是针对优选问题诸如最小成本计算、位址选择模型、节点连通性等都和图论中的最短路径问题等价，在方法论上它们有着很大程度的相似性与一致性。在求解网络图上节点间最短路径的方法中，目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在通过图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径。虽然这两种算法总的执行时间均为O(n3)，但是Floyd算法形式上更简单些。
1Floyd算法的基本思想
用两个矩阵来分别存储各对顶点间的最短路径长度和最短路径。
若顶点的个数为n，则最短路径长度矩阵为n阶方阵A，求解的过程是一个方阵A的序列：
A(-1)，A(0)，…，A(n-1)，
其中
A(-1)[i][j]=Edge[i][j]；A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][m]+A(k-1)[m][j]}，k=0,1,2,…,n-1；
A(k)[i][j]是从顶点vi到顶点vj经过中间顶点的序号不超过k的最短路径长度，A(n-1)[i][j]即是从顶点vi到顶点vj的最短路径长度。
2Dijkstra算法的基本思想
Dijkstra算法是一种按路径长度递增的次序产生的最短路径的算法。它把图中所有的顶点分为两组，第一组是已确定最短路径的顶点集合S，第二组是尚未确定最短路径的集合V-S；把V-S中的顶点按照最短路径长度递增的顺序逐个添加到
S中，添加过程中始终保持从V到S中每个顶点的最短路径长度都不大于从Ｖ到V-S中任何顶点的最短路径长度，直到从V出发可以到达的顶点都在S中为止。
Dijkstra算法对应顶点个数N进行多次迭代后就能获得任意两点间的最短路径。
3新算法的思想及证明
新算法采用从局部最优到整体最优的思想出发，放弃Floyd算法是从全局的角度对所有顶点进行n-1层计算的方式，我们知道所有顶点间路径集的最小者即是所关联两点间的最短路径，然后由已确定的最短路径集联合剩余顶点间备选路径集（简称备选路径集）的最小者，此最小者确定为最新的最短路径，来更新备选路径集，更新内容是对新产生的备选路径进行弃留判断，保留更短路径，放弃较长路径；重复以上的过程即可获得所有顶点间的最短路径。关于新算法有几点需要说明：
1）为何最短路径集中路径长度值是从小到大生成的。由算法过程知，当前已确定的最短路径集是由备选路径集的最小者构成的，而备选路径集的更新是通过备选路径集的最小者联合已确定的最短路径集来完成的，从而导致备选路径集的最小者其路径长度一定大于当前最短路径集中所有路径长度，此最小者确定为最新的最短路径，因此最短路径集中路径长度值一定是从小到大生成的。
2）为何备选路径集的最小者是新的最短路径。从局部最优到整体最优的思想出发，我们知道最新的最短路径的来源只能是两点间的直达路径和通过当前已确定的最短路径集形成的复合路径之间的最小者，因为最短路径集是由备选路径集的最小者构成的，并且已知其路径长度值是从小到大生成的，又因为备选路径集的更新是根据其最小者和已确定的最短路径集进行的弃留判断，如果备选路径集的最小者并非最短路径，那么真正的最短路径就只能通过非最短路径集的弧，此弧必为备选路径集中的非最小者，显然其路径长一定比最小者的大，故备选路径集的最小者一定是新的最短路径。
由上述两点得知，新算法在求解最短路径时是自小到大生成的，备选路径集的最小者一定是最新的一条最短路径，并且是已确定最短路径中最长的一条。备选路径集除最小者外，是经过已确定最短路径集优化过的其他顶点间的备选最短路径集，在特定条件下，可以作为最短路径的近似值。
4新算法的实现
新算法对应的数据结构：建立最短路径矩阵，其中每个元素包括路径长度值、路径描述、是否为最短路径等属性；建立剩余顶点间备选路径集队列（简称备选队列），其中每个元素包括路径长度值、路径描述等属性。
4.1初始化
1）对图的各个节点进行编号，初始化最短路径矩阵；
2）图中的弧按照弧值由小到大进行排序，建立备选队列；
3）备选队列出队列，并根据队首元素修改矩阵中对应元素的属性，设置为最短路径。
4.2算法主体
1）备选队列出队列，此变动同时映射到最短路径矩阵和剩余队列中；
2）根据队头元素，同时联合已确定的最短路径集，得到备选路径集，将路径和矩阵中现存的路径进行长度值比较，保留小者，放弃大者，此变动同时映射到最短路径矩阵和剩余队列中；
3）重复1-2步，直至备选队列为空，此时最短路径矩阵记录的即是任意两点间的最短路径。
4.3备选路径的弃留判断
假设队头元素对应的弧或者复合路径为aij，其值为vij。
将i行的非最短路径元素和j行对应列的最短路径元素进行比较，若
vim（非最短）-vjm（最短）>vij（最短），则修改vim（非最短）成vij（最短）+vjm（最短），否则vim（非最短）不变；
将j列的非最短路径元素和i列对应行的最短路径元素进行比较，若vmj（非最短）-vmi（最短）>vij（最短），则修改vmj（非最短）成vmi（最短）+vij（最短），否则vmj（非最短）不变。
4.4变动同时映射到最短路径矩阵和备选队列的过程
具体操作依据变动路径是否为最短路径分别处理：
若变动路径是最短路径，则以出队列来修正备选队列，同时以队头元素修改最短路径矩阵对应元素的长度值、路径描述是最短路径等属性值。
若变动路径是备选路径，则依据备选路径的弃留判断方法处理，当vim（非最短）、vmj（非最短）需要修改时，删除备选队列中的原vim、vmj并插入新的vim、vmj，同时以新的vim、vmj来修改最短路径矩阵对应元素的长度值、路径描述、非最短路径等属性值。
4.5算法主体的伪代码
typedefstruct{powerint,is_shortcutbit,char*path}Arc; ArcA[n+1][n+1];
typedefstruct{powerint,char*path,beginint,endint,char*path,Edge*next}Edge,*Shortcut_L;
//初始化矩阵;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)A[i][j]=(power,0,<i,j>);
对除去主对角线的矩阵元素按power进行排序，升序结果存储到链表Shortcut_L中。
//最短弧为最短路径
ListDelete(Shortcut_L,1,e);A[e.begin][e.end]=(e.power,1,e.path);
While(!ListEmpty(Shortcut_L))
{ListDelete(Shortcut_L,1,e);i=e.begin,j=e.end;A[i][j]=(e.power,1,e.path);
for(m=1;m<=n;m++)
{if(A[i][m].is_shortcut=0&&A[j][m].is_shortcut=1&&(A[i][j]+A[j][m]<A[i][m]))
{A[i][m]=((A[i][j].power+A[j][m].power,0,A[i][j].path+A[j][m].path);
Insert_List(Change_L,A[i][m]);//删除链表中的原vim并插入新的vim}
if(A[m][j].is_shortcut=0&&A[m][i].is_shortcut=1&&(A[m][i]+A[i][j]<A[m][j]))
{A[m][j]=((A[m][i].power+A[i][j].power,0,A[m][i].path+A[i][j].path);
Insert_List(Change_L,A[m][j]);//删除链表中的原vmj并插入新的vmj}}
ReSetElem(Shortcut_L,Change_L);//对备选路径进行弃留修改}
5效率分析
在理论上，新算法在空间效率方面需要一个备选队列，容量最大为n2-n。在时间效率方面，排序的时间为O(n2logn)，备选路径的弃留判断时间为O(n3)，队列变动映射时间为O(n2logn)，总的时间效率为O(n3)。尽管在理论上新算法的时间效率相对于经典算法没有提高，但是，由实际情况知，备选队列可以不用存储两点间的无穷大路径以及相对较大的路径，实际存储的空间远没有到达n2-n的规模。另外，备选路径的弃留判断必须是行或者列中最短路径和非最短路径元素的比较，在实际弧元素不是很多的情况下，可以采用建立最短路径和非最短路径链表来加速弃留判断过程，大大减少判断过程。在实际中，队列变动映射的时间效率，可以运用两个有序序列进行动态合并，也即删除旧结点的同时增加新结点，其时间效率为O(n)。就新算法的空间效率而言，备选队列本身也非必须存在，可以通过上述的非最短路径链表的链首结点记录本链最小值的方式，在行或列的链最小值中选择备选集的最小者，替代备选队列在算法中的原有作用，同时也减少了备选队列的排序时间，不过稍微增加每次选定备选集最小者的时间花费O(n)。
6应用
由于新算法有着不同于经典算法的特点，因此在如下方面具有应用价值：其一，由于最短路径是逐条生成的，并且是自小到大的生成，因此在需要对最短路径结果进行排序的情形下，就可以无需如同经典算法那样首先获得所有最短路径然后对结果再使用排序算法，新算法获得的结果即是自小到大有序的。其二，在弃留判断逐条生成最短路径的过程中，时间耗费经历了一个由少到多，再由多变少的过程，最大的频度为n，这样就便于控制算法的进度。其三，如若放弃备选队列，使用非最短路径链表的链首结点记录本链最小值的方式。那么在应对大规模矩阵时，在特定情况下，可以用已确定最短路径集优化过的非最短路径链表来得到不同近似程度的任意两点间最短路径结果，从而大大提高系统处理的速度。
作者简介：
孙平（1980-），女，汉族，吉林德惠人，基础数学、硕士研究生，沈阳建筑大学理学院讲师，研究方向：算法理论、推荐系统。
|
|
|
|
【对“硅谷杂志：任意两点间最短路径的新算法研究”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
