在拓扑排序的加权有向无环图上进行最长路径搜索，但有效路径的边数最大
Longest path search on a topologically sorted weighted directed acyclic graph, but with a maximum edge count for valid paths
我知道longest/shortest路径可以通过"processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges"在线性时间内找到，或者更简洁地说，拓扑排序并找到关键路径。
我的问题是我需要添加另一个限制，即有效路径中的最大边数。这使事情变得复杂，因为节点的 "maximum length obtained via any of its incoming edges" 可能涉及更多边，这意味着更高权重的节点可能不再可达，因为已经达到最大边数。
解决这个问题的正确方法是什么？线性时间还能解决吗？
只是 运行 常规算法。找到边数最多的路径后，只需停在那里并 return 您找到的解决方案。
当然，您可以使该路径更长，但这样会使最大边数无效，因此它不是有效的解决方案。
我想我找到了一个可以继续使用拓扑排序的解决方案。
像往常一样进行拓扑排序，然后采用关键路径方法，但是在计算到给定节点的最长路径时，不是只计算一条最长路径，而是为从 1 到最大边的每个路径长度找到最长路径一条有效路径，为这些得分最高的路径中的每一个创建一个顶点。
这基本上意味着您探索每个节点路径中所有可能的边数变化，这意味着最后得分最高的路径肯定是最长的路径。
我知道longest/shortest路径可以通过"processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges"在线性时间内找到，或者更简洁地说，拓扑排序并找到关键路径。
我的问题是我需要添加另一个限制，即有效路径中的最大边数。这使事情变得复杂，因为节点的 "maximum length obtained via any of its incoming edges" 可能涉及更多边，这意味着更高权重的节点可能不再可达，因为已经达到最大边数。
解决这个问题的正确方法是什么？线性时间还能解决吗？
只是 运行 常规算法。找到边数最多的路径后，只需停在那里并 return 您找到的解决方案。
当然，您可以使该路径更长，但这样会使最大边数无效，因此它不是有效的解决方案。
我想我找到了一个可以继续使用拓扑排序的解决方案。
像往常一样进行拓扑排序，然后采用关键路径方法，但是在计算到给定节点的最长路径时，不是只计算一条最长路径，而是为从 1 到最大边的每个路径长度找到最长路径一条有效路径，为这些得分最高的路径中的每一个创建一个顶点。
这基本上意味着您探索每个节点路径中所有可能的边数变化，这意味着最后得分最高的路径肯定是最长的路径。