首先,我想说这是我在 Stack Overflow 上的第一个问题,如果我的问题没有正确提出或者这是我不应该问的问题,请告诉我,以便我可以解决它(我已经读过导游,但你永远不知道!)
所以让我们开始吧:我正在尝试在有向非循环加权图中制定一个算法(权重可以是负数或正数)。该算法必须找到从特定节点开始、最多可以经过 N 个节点的权重最大的路径(如果可以获得更好的权重,可以使用更少的节点)。
我知道我必须使用动态编程来做到这一点,但我不知道如何做到这一点。我做了相当多的研究,我只提出了“从节点 u 到节点 v 的最长路径算法”,但这不是我想要实现的目标。
我熟悉 Dijkstra 算法,但我不认为这是我应该使用的。
非常感谢您阅读我的文章,并提前感谢您的帮助。
最佳答案
输入v、z的算法:
找到强连通分量,知道在从节点 v 开始的一段时间内是否存在具有正权值的循环,您可以返回无限
使用 dfs 对有向图进行排序
从叶子节点开始,返回最大值(weight_of_node(leave1, z),.....)
对于当前节点,打印它并选择通过递归函数计算出的权重最大的父节点。如果该节点只有一个父亲,则选择该父亲,如果该节点是 v,则返回 v 的权重并打印
现在所有选定的节点都已打印
*计算节点权重时
`节点权重(x, z):
如果 z==0
return - infinite
返回最大值(weight_of_node(father_node1),weight_of_node(father_node2),...) +current_node_weight`, z - 1)
关于algorithm - 动态规划: largest weight possible in a path of n nodes,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44640469/