一、问题描述

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

输入

顶点个数：n
边个数：m

  

 

  
1
  
2
 

输出

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

  

 

  
1
  
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中。

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

示例图各顶点最长路径计算结果如下：

参考

• 一文了解DAG有向无环图

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/109458448