algorithm - 计算有向图中得分最高的路径

Question

我有一个有向图，其中每个节点都有一个分数。从一个节点开始，我需要找到沿着一条路径可以达到的最高分。并非所有节点都可以成为最终节点。也可以重新访问一个节点，但只有第一次访问才计入分数。如何计算可达到的最高分数？

Answer 1

首先你可能会找到一个 strongly connected components图的。然后，您可以构建图形的压缩。

凝聚中的每个顶点的得分可能等于初始图中顶点得分的总和。

蓝色数字显示初始图中每个顶点的得分。黄色 - 图形浓缩。

如果凝聚的某些顶点包含最终节点，也将它们标记为终端。您还将拥有每个图形顶点到凝聚顶点的映射。

连接组件的概念很重要，因为如果您发现自己处于组件的一个顶点中，您可以轻松访问该组件的所有其他顶点以最大化得分。您可以任意多次重新访问每个顶点。

凝聚本身是一个有向无环图。您现在可以通过深度优先搜索维护函数来遍历压缩图

F_v = 0 - 如果 V 没有可达的终止顶点(下图右下角的顶点)

F_v = MAX_i(F_childv,i) + 分数_v - 否则

红色圆圈表示初始图中的顶点和凝聚被认为是终端。绿色数字表示凝聚图中每个顶点的 F 值。

您的问题的答案是对应于初始图中起始顶点的凝聚顶点的 F 值。总体时间复杂度为 O(N + M)，其中 N 是顶点数，M - 初始图中的边数。