改进的K最短路径算法在通信网络中的应用

摘要：

经典的K最短路径算法是最短路径算法中一个重要分支,它在交通网络的实时路径选择中起到了很重要的作用,为了将经典的K最短路径算法应用于通信网络中,我们对经典的K最短路径算法进行了改进.在求解K最大期望容量路径算法时,先对其进行权重转换,然后使用MPS算法;在求解K最大容量路径算法时,选取每个弧段源点,终点和弧段对应3个容量值最大的来进行标号;在求解K最大期望容量路径时,建立一系列的子网络,在每个子网络中先求出K最大可靠路径,对其容量进行排序,选出最小的,将大于该最小容量的所有弧集构成的网络定义为它的子网络,以此类推直到源点到目标点没有路径为止,对每个子网络中选取的K最大期望容量路径进行统一排序得到原网络中的K最大期望路径.通过网络通信实例,验证了算法的正确性和可行性.

关键词：物联网、K最短路、MPS算法、K最大期望容量路径

所属期刊栏目：59

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金91018008,61003268

在线出版日期：2013-12-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：534-538