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

Question

3

我有一个有向图，每个节点都有一个得分。从一个节点开始，我需要找到沿着路径可以获得的最高得分。并非所有节点都可以是最终节点。同时，可能会重新访问一个节点，但只有第一次访问计入得分。如何计算可获得的最高分数？

- zak

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivan Gritsenko · Accepted Answer

首先，您可以找到图的强连通分量。然后，您可以构建图的缩点图。

在缩点图中，每个顶点的得分可以等于原始图中顶点得分的总和。

蓝色数字显示了初始图中每个顶点的得分。黄色数字显示在图的缩减中。

如果一些缩减的顶点包含最终节点，则将它们标记为终端。您还将拥有每个图顶点到缩减中顶点的映射。

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

缩减本身是一个有向无环图。现在，您可以使用深度优先搜索遍历缩减图，并维护以下函数：

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

F_v = MAX_i(F_{child_v,i}) + score_v - 否则

红色圆圈表示初始图和缩点图中被认为是终止点的顶点。 绿色数字表示缩点图中每个顶点所具有的F值。

你问题的答案将会是与初始图中起始顶点对应的缩点图中的F值。总时间复杂度为O(N + M)，其中N是顶点数，M是初始图中的边数。