基于开关函数求广义最短通路的新算法

New algorithm for finding extended shortest path based on switching function

在分析现有求解最短通路的多种算法的基础上,给出了一种求广义最短通路的算法的理论依据.只需通过简单的环和运算求取图中的所有回路,然后选择要求的两顶点之间的任意一条通路,再进行一次环和运算,就可以求出图中任意两点间的最短通路长度.用实例验证了这种算法的正确性.与传统算法相比,该算法不仅可以求出一类广义最短通路,还可以获得相应的通路标识,而且减少了计算量.

The principle of a new algorithm to find extended shortest paths was given based on the analysis of existing algorithms. The length of the shortest path between any two appointed vertices was obtained in steps. Firstly all loops of the graph were obtained using ring sum, then any path between the two vertices was chosen and the operation of ring sum was carried out again. An example verified the validity of the algorithm. Compared with the traditional algorithms, the proposed algorithm can find a set of labeled extended shortest paths and reduce workload.