赵礼峰，黄奕雯

(南京邮电大学 理学院，江苏 南京 210046)

基于矩阵运算K短路径算法

赵礼峰，黄奕雯

(南京邮电大学 理学院，江苏 南京 210046)

最短路问题是复杂网络中的经典问题，其求解算法层出不穷，各有优缺点。经典的算法包括Dijkstra算法、Ford算法和Floyd算法等，只能求解两节点间的一条最短路径。在实际生活中，还需要在大型网络中限定一些前提条件求解两点间次短、渐次短的路径问题。为此，提出了一种对距离矩阵和路径矩阵的迭代、替换算法，即从一个节点出发寻找其后继节点，同时通过比较路径长短得到两点间最短路径、次短路径和渐次短路径，并不断重复、替换。为验证所提算法的有效性，以一个大型网络的应用作为实例，应用Matlab对所提算法进行了仿真实验验证。仿真结果表明，所提算法能够在复杂大规模随机网络中满足求解指定顶点间最短、次短和渐次短路径的需要，具有较好的有效性和适用性。

次短路径；渐次短路径；距离矩阵；路径矩阵

0 引 言

最短路径问题是复杂网络中一大经典问题，它的应用领域十分广泛，如通信网络、物流运输、地理信息系统、军事运筹学和旅行规划等等[1]。经典算法[2]却只能解决两节点间一条最短路，而在这些实际运用中，往往不仅仅考虑一条最短路径，还要根据实际情况及具体要求选择其次短路径、渐次短路径。比如说在旅行线路的规划问题上，所要选择的路线不一定是距离最短的路线，还要考虑实际路况、天气、经济效益等因素，那么就需要筛选出不止一条短路径。……