有向网络最长距离的矩阵算法

对于无多重弧的n阶赋权有向图,引入距离矩阵A,将此矩阵看作取大-加代数(R∪{-∞},max,+)上的矩阵,证明了只要任一回路的权非正,则An-1的分量ai(jn-1)就是顶点i到j的最长距离,且此最长距离必在某条路径上取得。