最短路线问题的矩阵解法

Method with Matrices to Solve the Shortest Path Problems

给出了求最短路线问题的直接解法,利用矩阵的循环移位变换,构造集合的笛卡儿积,把所有可能的路线看成是始点集合与终点集合的笛卡儿积的子集.把距离定义为笛卡儿积上的函数,结合Matlab软件,列出由始点到终点的所有路线,并计算出对应的距离,进而求出最短路线和最短距离.所给程序可以作为模型推广应用到同类问题的求解中.

This paper presents a direct solution for problems of the shortest path, using cyclic shift transformation of matrices, construct the cartesian product of given sets, take the set of all possible routes as a subset of the cartesian product of starting points sets and end points se, the distance is defined as the function of this cartesian product, combined with the Matlab software, list all the routes from the starting point to the end point, then calculate the corresponding distances, finally find the shortest route and the shortest distance. The given programming can be applied in solving the same kind of problems.