具有确定弧数最长路的算法

ALGORITHMS FOR FINDING THE LONGEST PATH WITH AN EXACT NUMBER OF ARCS

给出了寻求强连通赋权有向图中从一顶点到任意顶点间具有确定弧数的最长路 (最短路 )和最长初等路 (最短初等路 )的算法 ,并对算法的有效性进行了讨论。该算法对扩展 Karp和Cohen的结果——强连通赋权图中最小平均权的算法和线性离散事件系统的闭环系统矩阵在极大代数意义下的特征值的算法 。

The algorithms for finding the longest path (the shortest path) and the longest elementary path (the shortest elementary path) with an exact number of arcs from one vertex to each of the vertices on a strongly weighted directed graph are given. The effectiveness of the algorithms is discussed. The algorithms have concrete significance for developing Karp's and Cohen's conclusions which are the algorithms for finding both the minimum cycle mean on a strongly weighted graph and the eigenvalue of the closed loop system matrix of the linear discrete event system in the sense of max algebra.