本文共 843 字，大约阅读时间需要 2 分钟。

一、问题描述

问题：求解有向无环图(DAG)中所有顶点的最长路径。

输入

顶点个数：n边个数：m

输出

每个顶点的起始边对应的索引：outVertices[n]每条边的终点及该边的权重：outEdges[m*2]:

• 1）outVertices[0] = 0且outVertices[1] = 4, 因此以顶点0为起点的边共有4条，对应的终点记录在outEdges[0:3]，分别为1/2/4/5，边的权重分别为4/7/1/8。
• 2） outVertices[1] = 4且outVertices[2] = 6, 因此以顶点1为起点的边共有2条，对应的终点记录在outEdges[4:5]，分别为2/5，边的权重分别为2/10。
• 3） outVertices[2] = 6且outVertices[3] = 6, 因此没有以顶点2为起点的边。

二、实现算法

串行算法基于x86平台测试

首先，定义两个数组longest[n]和inDegree[n]，分别表示每个顶点的最长路径和入度， longest[n]初始化为0，接着依次进行：

1. 每个顶点的入度为以该顶点为终点的边的个数，因此遍历outEdges可计算出每个顶点的入度，示例图入度计算结果如下：

2. 遍历所有顶点的入度，记录入度为0的顶点到队列 $V_{d}one$中，这些顶点的最长路径为0，对于示例图：Vdone = {3}

3. 循环处理Vdone队列直到队列为空：从Vdone队列取出顶点Vi ，对于以Vi 为起点的边Vi -> Vj ， 更新longest[Vj] = max(longest[Vj], longest[Vi]+weight(Vi -> Vj))。 如果边Vi-> Vj是顶点Vj的最后一条入边，则longest[Vj]已确定，添加Vj到队列Vdone中。

对于示例图，算法处理步骤如下：

参考

转载地址：http://fjnaf.baihongyu.com/