java实现最短路径算法-基于图分解的并行最短路径搜索算法设计并行Dijkstra

引言最短路径问题一直是交通运输问题中应用的一个研究热点。首先，任何一种交通量分配法都是以求解最短路径为基础；其次在绝大多数交通分配方法中，最短路径的计算占据了全部计算时间的最大比例。MichelleR.Hriba在1997年的实验中指出：在单处理器的IntelParagon机上计算含有970个结点的交通网络中的平衡配流问题时，至少有95%的计算时间用于求解最短路径。在上世纪50年代末，Dijkstra提出了按路径长度不减次序产生的最短路径的算法，虽然人们一直采用，但算法在结点数目多的情况下效率明显很低。随着计算机处理数据量的逐渐增多，传统的串行计算机的负荷也逐渐加重，已经不能满足大规模最短路径求解的实时要求。运行在服务器端的最短路径算法必须向基于图分解的并行算法的方向发展，才能满足大量的实时最短路径查询的需要。并行计算所提供的存储与计算资源使得可以在合理的时间内求解最短路径问题。并行最短路径搜索算法设计并行Dijkstra算法思想是首先将大量的结点进行划分，为了实现负载平衡，均匀划分成若干个数目相同的结点集合，并分配到不同的处理器上，然后各个处理器并行地求解各自所分结点到起始结点的局部最小值，接着其中一个处理器将这些局部最小值收集起来，进行一次比较，求出全局最小值java实现最短路径算法，标记该最小值的位置，表明已经找到它的最短路径，再将这个全局最小值广播给其他各个处理器，各处理器根据所得到的最小值同时进行更新，然后再求各自的局部最小值，这样一直循环，直到所有的结点都被标记为止。下面给出并行最短路径搜索算法的设计步骤：（）首先将结点进行划分，每个处理器划分n=N/p个结点（其中N表示总结点数java实现最短路径算法，p表示处理器的数目）。（2）每个处理器并行求解离起始点距离的局部最小值，然后由其中一个处理器收集这些分布在其他处理器的局部最小值及相对应的结点编号，再由该处理器求出这些局部最小值中的较小值，即为全局最小值min。标记该最小值的位置index，然后再将这一最小值min及所对应结点的下标位置index播给其他各个处理器。（3）每个处理器根据这个全局最小值独立进行更新，更新如下：如果min+W（v，index）