基于优化的Floyed算法前r条最短路径的实现

最短路径的算法应用在很多领域,基本的Floyed算法是解决任意两点之间的最短路径,在实际应用中会要求给出前r条最短路径,以便决策,从中选择一条最佳的路径,文章在分析Floyed算法的基础上,给出改进算法,求解前r条最短路径,并且优化了Floyed算法的时间代价,使其对稀疏图的效率更高。

To Figure Out the First Rth Shortest Path Based on Optimal Floyed Algorithm

The shortest path algorithm is applied in many fields.The normal Floyed shortest path algorithm is supposed to deal with the shortest path between every two dots.Based on the analyzing of Floyed shortest path algorithm,the article presents the optimal algorithm of Floyed shortest path algorithm that can give the first Rth shortest path between every two dots.And also,the article demonstrates some improvement,which can be used to make the algorithm quicker,particularly when it deals with the sparse graph.