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=(a_ij)称为G的P邻接矩阵，其中：若V_i邻接V_j，a_ij={<ij,L(ij)>};否则 a_ij= ¢，其中L（ij）=w_ij 。
定义3 设M¹为简单加权图G的P邻接矩阵，M为将M¹中所有路删去左边首数字后而得到的矩阵，M^k_=Mm-1©M，W为ÙM^m中只保留源点到汇点的最长路径项得到的矩阵，则W中的所有路径均为关键路径。
2 算法
如下算法求出所有关键路径。
算法步骤：
(1)构造图G的P邻接矩阵 ；
(2)根据M¹构造M；
(3)删去M¹中除去第一行之外的所有行得到的矩阵仍然记为M¹；
(4)根据公式M^k=M^m-1©M 构造秩为k的基本P矩阵M^k(k=2，…,n-1）且只保留各顶点之间的最长路径项；
(5)计算W=ÙM^m且只保留源点到汇点的最长路径项；
(6)输出所有关键路径。
本人刚学数据结构不久，遇到这个算法不知如何程序实现，希望有兴趣的朋友帮忙写出代码，最好是C++的，不胜感激。