Matrix Optimization Algorithm Based On Matrix Operation

The shortest path problem,as a classical problem in graph theory and complex network,is also present in large numbers of aspects in daily life,such as communication network,transportation network,traveling salesman problem.And the algorithm to solve the shortest path problem is also emerging.However,Dijkstra algorithm can only get the shortest distance between a pair of nodes,Ford algorithm can only get the shortest path of the fixed origin vertex,and Floyd algorithm is so cumbersome.These algorithms are only able to solve one shortest path between two vertices.However,in real life,we sometimes need to find the second shortest path,the third shortest paths between some vertices because of some given prerequisites.Based on the above disadvantages,this paper presents the shortest path optimization algorithm based on the matrix operation,the main contents are as follows:Firstly,aiming at the improvement of Ford algorithm,A new Matrix elimination algorithm is proposed to find the path from a fixed origin vertex to the other vertices.Including these situation without any other vertices,through a vertex,through two vertices iteration step by step.Find the shortest path from the fixed origin vertex to the rest of the vertices.Secondly,an improved Floyd algorithm based on matrix customization is proposed.The algorithm obtains a road weighting correction matrix which represents the distance between two vertices by custom matrix operation.Then compared and choose the smaller elements between two matrices to form the shortest path matrix.And through MATLAB simulation,the algorithm is extended to random large-scale network,through the run-time line graph shows that the algorithm's running speed is significantly better than traditional algorithms when the number of vertices reaches a certain numbers particularly in sparse network.Finally,the practicability of the algorithm is illustrated by the real application.Thirdly,proposing the iterating and displacement algorithm that find the first shortest path,the second shortest path and the third shortest path between two nodes by finding the successor node from a starting node continuously.And illustrate the practical value with a practical example.Finally,using MATLAB simulation to illustrate that it can be used in the large-scale networks.