1 相关概念
这里提出P集合，P矩阵和基本P矩阵的概念，并定义了P矩阵的两种运算，讨论其性质。为本文提出的求关键路径算法奠定了基础。
定义1 给定简单加权图G=<V,E,W>,I为G的P集合，若<x,L(x)>、<y,L(y)> 属于I,在I上定义运算 如下：
当x与y没有公共字符时，<x,L(x)>©<y,L(y)>=<x∥y,L(x)+L(y)>;否则<x,L(x)>©<y,L(y)>=¢ ,其中∥为字符的连接运算。
定义2 给定简单加权图G=<V,E,W>,n阶方阵A=(aij)称为G的P邻接矩阵，其中：若Vi邻接Vj，aij={<ij,L(ij)>};否则 aij= ¢，其中L（ij）=wij 。
定义3 设M1为简单加权图G的P邻接矩阵，M为将M1中所有路删去左边首数字后而得到的矩阵，Mk=Mm-1©M，W为ÙMm中只保留源点到汇点的最长路径项得到的矩阵，则W中的所有路径均为关键路径。
2 算法
如下算法求出所有关键路径。
算法步骤：
(1)构造图G的P邻接矩阵 ；
(2)根据M1构造M；
(3)删去M1中除去第一行之外的所有行得到的矩阵仍然记为M1；
(4)根据公式Mk=Mm-1©M 构造秩为k的基本P矩阵Mk(k=2，…,n-1）且只保留各顶点之间的最长路径项；
(5)计算W=ÙMm且只保留源点到汇点的最长路径项；
(6)输出所有关键路径。
本人刚学数据结构不久，遇到这个算法不知如何程序实现，希望有兴趣的朋友帮忙写出代码，不胜感激。