解决最短路问题的算法层出不穷，其中最经典的要数Dijkstra算法和Floyd算法。但Dijkstra算法只能得出一对节点间的最短距离，而Floyd算法计算过程十分繁琐。为解决这两种经典算法中的缺陷，提出一种基于矩阵自定义运算的Floyd改进算法。该算法通过自定义矩阵运算得出一个表示两两节点间距离的路权修正矩阵，再用路权修正矩阵与原距离矩阵进行比较，选择两矩阵中对应较小元素组成当前最短路权矩阵，再通过有限次的迭代，从而得到各顶点间的最短路。通过MATLAB仿真，将该算法推广到随机大规模复杂网络中，通过运行时间折线图表明，该算法在节点达到一定数量后运行速度明显优于传统算法，且在稀疏网络中运行效率非常高，说明了该算法的有效性。最后，通过具体应用说明了该算法的实用性。%The algorithm to solve the shortest path problem is endless,and the algorithm of Dijkstra and Floyd is the most typical. Howev-er,the Dijkstra algorithm can only get the shortest distance between a pair of nodes,and Floyd algorithm is very cumbersome. For solving their defects in two classical algorithms,an improved Floyd algorithm is proposed based on matrix custom operation. It obtains a modified matrix between two nodes by using a customized matrix calculation,and then compares the modified matrix with the original distance ma-trix,selecting the smaller matrix elements for composition of the shortest path weight matrix. Through finite iteration,the shortest path is obtained between each vertex. By the MATLAB simulation,the algorithm is extended to stochastic large-scale complex networks. The running time line chart shows that this algorithm runs faster than traditional algorithm after a certain number of nodes,and in sparse net-work,the efficiency is particularly high,which shows the its effectiveness. Finally,by using the specific application,the feasibility of the algorithm is verified.
展开▼
