如何在加权图中找到权重和最大的路径？

Question

我有一堆物体，每个物体都有等级、重量，还有可能连接到下一个等级的物体。我想知道怎么找到一条“最重”的路径，也就是重量总和最大的那条路径。

当然，我也想知道有哪些书可以教我如何实际处理图形相关的内容。

Answer 1

我推荐的书是史蒂夫·斯基纳的《算法设计手册》。里面有一章专门讲图的内容，非常不错。

Answer 2

我假设你只能往图的下层走。

注意这个图的结构像一棵树。你可以用递归的方法来解决这个问题：

heaviest_path(node n) = value[n] + max(heaviest_path(children[n][0]), heaviest_path(children[n][1]), etc)

其实可以用动态规划来更简单地优化这个过程。

从最底层的孩子开始，他们的 heaviest_path 就是他们自己的值。把这些值记录在一个数组里。然后计算上面一层的 heaviest_path，再往上层计算，依此类推。

Answer 3

你的图是无环的，对吧？（我假设是这样，因为一个节点总是指向下一个层级的节点）。如果你的图可能有任意的环，那么找到最长路径的问题就变得非常复杂，只有暴力搜索才能解决。

回到问题上来——你可以通过找到每个节点到达它的最长路径来解决这个问题。因为你已经有了一个有向无环图（DAG）的拓扑排序（就是这些层级本身），所以找到路径是很简单的：

1. 对于每个节点，记录到达它的最长路径的成本，以及在这条路径上最后一个节点。最开始，这些信息都是空的（不过可以用一个特殊值，比如负数，来简化后面的代码）

2. 对于第一层的节点，你已经知道到达它们的最长路径的成本——就是零（而且它的父节点是 None）

3. 对于每一层，把路径信息传递到下一层——这和普通的最短距离算法类似：

   for level in range(nlevels):
       for node in nodes[level]:
           cost = the cost to this node
            for (neighbour_vertex, edge_cost) in (the nodes edges):
                alt_cost = cost + edge_cost
                if  alt_cost < cost_to_that_vertex:
                    cost_to_that_vertex = alt_cost