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

Question

我有一堆对象具有级别,权重和0或更多连接到下一级别的对象.我想知道如何获得"最重"的路径(具有最大的权重总和).

我当然也很想知道,有哪些书教会我如何以实际的方式处理图形.

Answer 1

你的图表是非循环的吗？(我认为是这样,因为节点总是指向下一级别的节点).如果您的图形可以具有arbritrary周期,则找到最大路径的问题将变为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