基于“矩阵乘法”的网络最短路径算法

Shortest Path Problem Algorithm in Network Based on Matrix Multiplication

网络最短路径问题可以作为许多实际应用问题的模型,但传统的求解算法其迭代过程复杂.本文描述了基于矩阵乘法的最短路算法,其时间复杂度与Dijkstra算法相同.在给定的一个网络图中,在不改变网络图中的最短路的条件下,删除"多余"的结点或边,可以达到简化网络图和提高求解速度的目的,从而降低计算复杂性.最后,研究了该方法在最短路径问题和旅行商问题中的应用.实例表明,这种算法与传统的动态规划技术相比,具有运算简便、易于理解的优点.

Shortest Path Problem in network can be acted as a model for many application problems, but the iteration process of the conventional solution algeorithm is complex. In this paper, the shortest path algorithm based on the matrix multiplication in a weighted-graph are described,and its time complexity is as same as Dijkstra algorithm. In a given network graph, this algorithm delete spare nodes or edges and reach the goal that reduced network graph and improved speed of solving problem under the condition of unchanged shortest parth. Finally, we give examples,e.g. Traveling Salesman Problem, shortest path problem,to illistrate its advanteges, possessing merits of simple operation and easy understanding, compared with dynamic programming technology.