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

Question

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

Answer 1

首先您可能会找到一个 strongly connected components 的图表。然后你可以构建一个condensation的图。

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

蓝色数字表示初始图中每个顶点的得分。黄色-图中凝结。

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

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

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

来遍历压缩图

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

F_v = MAX_i(F_{childv, i}) + 分数_v - 否则

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

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