任意两点最短距算法研究.docVIP

本文摘自 硅谷 杂志，最短路径问题是图论研究中的一个经典算法问题，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）对图的各个节点进行编号，初始化最短路径矩阵