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

Question

我有一堆对象，它们具有级别、重量以及与下一级对象的 0 个或多个连接。我想知道如何获得“最重”路径(权重总和最大)。

当然，我也很想知道，哪些书教我如何以实用的方式处理图形。

Answer 1

你的图是非循环的吧？ (我想是的，因为一个节点总是指向下一层的节点)。如果你的图可以有任意环，寻找最大路径的问题就变成了 NP 完全问题，暴力搜索成为唯一的解决方案。

回到问题 - 您可以通过为每个节点找到通向它的最重路径来解决这个问题。由于您已经对 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