拓扑排序求最长路径

拓扑排序是一种对有向无环图（DAG）进行排序的算法，可以被用于解决诸如任务调度和依赖关系的问题。在一些实际问题中，我们需要求解DAG上的最长路径，比如在一个项目中，需要确定完成该项目所需要的最长时间。本文将介绍如何使用拓扑排序来求解DAG的最长路径。

什么是拓扑排序？

在介绍如何使用拓扑排序求最长路径之前，我们需要了解什么是拓扑排序。拓扑排序是一种对DAG进行排序的算法，它可以将DAG中所有的节点按照拓扑顺序排列。拓扑排序的过程中，会将入度为0的节点放到排序列表的最前面，并将出边从该节点指向的节点的入度减1。通过不断重复这个过程，直到所有的节点都被加入到列表中为止。

使用拓扑排序求解最长路径

求解DAG的最长路径的一种常用方法是动态规划，但是这种方法会比较复杂。而使用拓扑排序求解最长路径是一种更加简单直接的方法。具体步骤如下：

1. 将DAG进行拓扑排序，并将所有的节点的最长路径和最长前驱（即路径长度最长的前一个节点）初始化为0。

2. 对于排序列表中的每个节点，将它的最长路径设置为所有前驱节点的最长路径加上该节点的边权值。将该节点的最长前驱设置为它的所有前驱节点中路径长度最长的那个。

3. 遍历所有的节点，找到最长路径所在的节点，以及该节点向前的所有节点，最长路径即为该节点的最长路径。

实例

假设我们需要求解下面这个DAG的最长路径：

节点 | 入边 | 出边

--- | --- | ---

0 | - | 1, 2

1 | 0 | 3

2 | 0 | 3

3 | 1, 2 | 4, 5

4 | 3 | 6

5 | 3 | 6

6 | 4, 5 | -

首先对该DAG进行拓扑排序得到排序列表为[0, 1, 2, 3, 4, 5, 6]。将所有节点的最长路径和最长前驱初始化为0，然后按照排序列表的顺序依次计算每个节点的最长路径和最长前驱。

- 对于节点0，它的最长路径为0，最长前驱为0。

- 对于节点1，它的前驱节点为节点0，节点0的最长路径为0，所以节点1的最长路径为节点0的最长路径+节点1到节点0的边的权值1=1，最长前驱为0。

- 对于节点2，它的前驱节点为节点0，节点0的最长路径为0，所以节点2的最长路径为节点0的最长路径+节点2到节点0的边的权值2=2，最长前驱为0。

- 对于节点3，它的前驱节点为节点1和节点2，这两个节点的最长路径分别为1和2，所以节点3的最长路径为max(1, 2)+节点3到节点1的边的权值3=4，最长前驱为1。

- 对于节点4，它的前驱节点为节点3，节点3的最长路径为4，所以节点4的最长路径为节点3的最长路径+节点4到节点3的边的权值4=8，最长前驱为3。

- 对于节点5，它的前驱节点为节点3，节点3的最长路径为4，所以节点5的最长路径为节点3的最长路径+节点5到节点3的边的权值3=7，最长前驱为3。

- 对于节点6，它的前驱节点为节点4和节点5，这两个节点的最长路径分别为8和7，所以节点6的最长路径为max(8, 7)=8，最长前驱为4。

从上面的计算中，我们可以得出最长路径为8，该路径经过的节点为[0, 1, 3, 4, 6]。

结论

使用拓扑排序可以方便地求解DAG的最长路径。该方法主要分为三步：拓扑排序、计算每个节点的最长路径和最长前驱、找到最长路径所在的节点和它向前的所有节点。通过该方法，我们可以在不使用动态规划的情况下，求解DAG的最长路径。