我知道最长/最短路径可以通过“按拓扑顺序处理顶点，并将每个顶点的路径长度计算为通过其任何传入边获得的最小或最大长度”来在线性时间内找到，或者把它更简洁，拓扑排序并找到关键路径。
我的问题是我需要添加另一个限制，即有效路径中的最大边数。这使事情变得复杂，因为节点的“通过其任何传入边获得的最大长度”可能涉及更多边，这意味着由于已经达到最大边，因此可能不再可以到达更高权重的节点。
解决这个问题的正确方法是什么？它仍然可以在线性时间内解决吗？
问问题
672 次
2 回答
1
我想我已经找到了一个解决方案，可以使仍然使用拓扑排序成为可能。
像往常一样进行拓扑排序，然后是关键路径方法，但是在计算到给定节点的最长路径时，不是只计算一条最长路径，而是在有效路径中找到从 1 到最大边的每个路径长度的最长路径，创建这些最高得分路径中的每一个的顶点。
这基本上意味着您探索到每个节点的路径中所有可能的边数变化，这意味着最后得分最高的路径肯定是最长的路径。
于 2016-05-24T13:41:16.073 回答
-1
只需运行常规算法。一旦找到具有最大边数的路径，只需停在那里并返回您找到的解决方案。
当然，您可以使该路径更长，但它会使最大边数无效，因此它不是有效的解决方案。
于 2016-05-24T11:59:22.153 回答