一种基于动态规划法的关键路径算法

詹泽梅

摘要：数据结构是计算机及其相关专业的一门重要专业课。在数据结构课程中，关键路径是一个难点问题。本文首先概述了关键路径问题，接着介绍了动态规划法，分析其求解关键路径的可行性，最后重点描述了采用十字链表存储有向图时的一种基于动态规划法的关键路径求解算法。

关键词：关键路径;动态规划法;十字链表;AOE-网

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）31-0215-03

1关键路径

有向无环图可用于描述一项工程的施工流程。在有向无环图中，既可用顶点表示子工程（又称活动），也可用有向边表示子工程。当用有向边表示子工程时，边上的权值可表示完成子工程所需的时间、价钱等信息。这种边表示子工程活动的有向无环图就称为AOE-网（ActiviIy On Edge），即边表示活动的网。在AOE-网中，有且仅有一个人度为零的顶点，它称为源点，代表工程的开始点;有且仅有一个出度为零的顶点，它称为汇点，代表工程的结束点。

对于一项工程，人们通常要估算完成工程所必须的最短时间。当在计算机中用AOE-网描述工程施工流程时，完成工程所必须的最短时间就等于AOE-网中源点到汇点最长路径的长度。此处路径长度是指路径上各活动持续时间之和，即各有向边上的权值之和。路径长度最长的路径叫作关键路径。估算整个工程完成所必须的最短时间，实际上就是要求AOE-网中的关键路径。

例如，图1是一个AOE-网，它表示该工程可分为8个子工程活动。活动之间的施工先后关系是：工程一开始就可执行活动a1、a2、a3，活动a1完成后可开始执行活动a5，活动a3完成后可开始执行活动a4、a7，活动a2、a4完成后可开始执行活动a6，活动a5、a6完成后可开始执行活动a8，活动a7、a8完成后则整个工程完成。有向边上的权值表示完成活动所需要的时间。顶点A是工程开始点（源点），顶点F是工程结束点（汇点）。完成该工程所需要的最短时间等于源点A到汇点F的最长路径的长度。此AOE-网的最长路径有两条：ABEF和ADCEF，路径长度为10，即完成整个工程的最短时间是10。这两条路径都是关键路径。

2动态规划法

动态规划法是求解多阶段决策最优化问题的一种常用方法。它所解决的问题需要满足最优性原理。最优性原理简单地说就是原问题的最优解由各个子问题的最优解构成。

关键路径问题就是求AOE-网中源点到汇点的最长路径，假定AOE-网的源点s到汇点t的最长路径是s，x1，X2，…，Xp，t，则路径s，x1，X2，…，Xp一定是源点s到顶点Xp的最长路径。可用反证法证明关键路径问题满足最优性原理。如果路径s，x1，x2，…，Xp不是源点s到顶点xp的最长路径，存在另一条路径s，Yl，Y2，…，Xp的长度大于路径s，x1，x2，…，xp的长度，则路径s，Y1，Y2，…，Xp，t的长度就大于路径s，x1，X2，…，Xp，t的长度，这就与最初的假设“假定AOE-网的源点s到汇点t的最长路径是s，x1，X2，…，Xp，t”相矛盾。所以关键路径问题满足最优性原理，可用动态规划法求解。

动态规划法将待求解问题分解成为若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段。该方法的求解过程通常可分为三个阶段：划分子问题、设定动态规划函数、计算各个子问题并填写表格。

3基于动态规划法的关键路径算法

3.1算法分析

动态规划法求解问题时首先是划分子问题。对于关键路径问题如何划分子问题呢？假设我们用Cxy表示有向边上的权值，用Dis（s，v）表示源点s到顶点v的最长路径长度。假设顶点u是顶点v的前驱顶点，则源点s到顶点v的最长路径长度应为Csv和Dis（s，u）+Cuv中的最大值。即有以下等式成立。

由于源点s到顶点v的最长路径与源点s到顶点v的前驱顶点u的最长路径相关，所以子问题可设定为求源点到某顶点的最长路径。动态规划函数可使用上述等式。

动态规划法的第三个步骤是计算各子问题并填表。此问题中就是要计算源点到各顶点的最长路径。对于AOE-网中的各顶点，应按什么顺序求解子问题呢？显然前驱顶点的最长路径应先求，所以应按照图中有向边指示的先后顺序求各顶点的最长路径，对于没有先后顺序的顶点可按任意顺序求解。换句话就是要按图中顶点拓扑有序序列中的先后顺序求解源点到各顶点的最长路径。

3.2图的存储表示

关键路徑算法的设计与图的存储结构密切相关。本问题中的有向图如何存储呢？由于在求源点到各顶点的最长路径时，要按拓扑有序序列中的顶点顺序求，那么就要对有向图中顶点进行拓扑排序。在拓扑排序过程中，需要知道从各顶点出去的有向边（弧），所以在图的存储结构中，应能方便找到从各顶点出去的弧。又由于源点到某顶点v的最长路径与源点到v的前驱顶点的最长路径相关，所以在图的存储结构中，要能方便找到任意一顶点的前驱顶点。十字链表存储结构能很好地满足这两个要求，所以我们以十字链表作为本问题中图的存储结构。图1所示有向图的十字链表存储结构如图2所示。

3.3关键路径算法

求关键路径之前，首先要求出AOE-网的一个拓扑有序序列，假设用数组TopoV存储拓扑有序序列中各顶点的位置下标。可按拓扑排序的方法求TopoV数组值。求解步骤如下：（1）找AOE-网中入度为0的顶点并存储在数组TopoV中;（2）删除以该顶点为弧尾的弧。重复执行（1）（2）两步，直至找不到人度为0的顶点为止。

然后按算法1求AOE-网的源点到各顶点的最长路径信息，最后按算法2输出关键路径和其长度。

算法1中MaxLenV数组存储源点到每个顶点的最长路径信息，其中MaxLenV[i1记录源点到拓扑序列中第i+1个顶点的最长路径信息，该顶点在有向图的十字链表的vertices数组中的位置下标为TopoV[i]。顶点的最长路径信息类型定义如下：

4总结

动态规划法是求解最优化问题的一种常用算法设计技术。关键路径问题的解满足最优性原理，因此可用动态规划法求解。本文在有向图采用十字链表存储方式下，设计了一种基于动态规划法的关键路径算法，该算法能正确的输出源点到汇点的关键路径及其长度。