K优路径的一种求解算法与实现

A Fast Algorithm and It's Implementation of Finding the K-Shortest Paths

求解最优路径的算法已经比较成熟,但国内外求解K优路径的算法还未见到。在作战指挥中,通常需要人们能够根据战场情况提供部队行动路线的多个方案供指挥员决策。针对这一军事需求,论文提出了一种求解K优路径的算法,给出了相应的数据结构和算法实现,同时从实现的角度对Dijkstra算法进行了改进。

There is a classical algorithm of finding the shortest path,Dijkstra.But no algorithm for finding k-shortest paths in our country or abroad.In military application,the commander always need to know the way through which his unit could reach the garrison in time bypassing the unavailable region and passing the necessary depot,and further more,he need several standby layouts.So,to meet this requirement ,in this article,the authors give an algorithm for find-ing k-shortest paths,offer the data structure for it,and at last give out the implement of this algorithm and the Dijk-stra.