矩阵方法求赋权图中最短路的算法

The algorithms to solve shortest paths in weight graphs with matrix methods

目的 给出一些计算赋权图中任意两个节点之间最短路的算法。方法 利用矩阵方法。结果 给出了赋权图中任意两点之间最短路的算法;任意两点之间在含有最少边数情况下的最短路算法;赋权图中的所有最短路算法,以及前N条最短路的算法。结论 所研究的算法解决了传统算法的某些不足,因基于矩阵运算,程序设计简单,实用性强。

AimSome algorithms to find the shortest paths in weighted graphs are studied.MethodsBased on the matrix calculation,the algorithms are presented.ResultsThe algorithms include the follows: the algorithm to find the shortest path between any pairs of nodes;the algorithm to find the shortest path between any pairs of nodes under the condition of the shortest path including minimum edges; the algorithm to find all shortest paths between any pairs of nodes;and the algorithm to find the N shortest paths between any pairs of nodes.ConclusionBecause the algorithms in the paper use the matrix as the tools, the design of the program is easy. Validation of the algorithm is proved in practices.