一种基于移动IPv6路由寻址的最短路径优化算法

An Optimization of the Shortest Path Algorithm Based on the Routing of Mobile IPv6

移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3)。本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法。该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<<n2,此算法的时间复杂度O(e*n)<<O(n3),比传统算法具有更明显的优势。

The routing of Mobile IPv6 is a shortest path problem, the most famous of the two shortest path algorithm are Dijkstra algorithm and Floyd algorithm. Both the two algorithms have the same time complexity as O （n^3）. Through the research and analysis of these two classic algorithms, the essay aims to get an optimization algorithm for the shortest path, and time complexity is O（e^＊n）. In the connectivity map, the algorithm can be less than Floyd algorithm nearly 50 percent of the number of iterative; the time complexity of the algorithm is （e ^＊ n）, in non-connectivity map, e 〈〈n2, and it has obvious advantages than traditional algo- rithm.