0

我有一张像树一样的图表（见下面的粗图。不幸的是无法发布图片）。这是一个 DAG，所有的边都应该指向右边。所有上升的边都将具有负权重，所有下降的边将具有正权重。图表的直径将为 48，但高度可能限制为 5、7 或其他，具体取决于场景。

        O-O...
       / X 
      O-O-O...
     / X X
    O-O-O-O...
     \ X X
      O-O-O...
       \ X
        O-O...

我想在 48 个节点之后找到从起始节点到最后一个节点的最长路径。经过一些研究，似乎我可以否定所有值（* -1），使用 Bellman-ford 找到最短路径，这应该给我线性时间最长的路径？（http://courses.engr.illinois.edu/cs473/sp2011/lectures/04_class.pdf第 37/40 页）

我知道如果你否定边缘，如果它们最初都是积极的，它应该工作。但是，如果其中一些是正面的而其中一些是负面的，这仍然适用吗？

4

0 回答 0