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

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

Shortest Path Problem Algorithm in Network Based on Matrix Multiplication

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 uncha...