题
什么是最好(有关性能)的方式计算的关键路径中的一个向环图时的节点的曲线图具有的重量吗?
例如,如果我有以下结构:
Node A (weight 3)
/ \
Node B (weight 4) Node D (weight 7)
/ \
Node E (weight 2) Node F (weight 3)
关键路径应该是A->B>F(总重量:10)
其他提示
我会解决这个动态程序。找到的最大成本从S T:
- 拓扑种节点的曲线图作为S=x_0,x_1,...,x_n=T.(忽略任何节点可以达到或将达到从T)
- 最大的成本从S S重S.
- 假设你已经计算的最高费用从S x_i我 < k,最大的成本从S x_k的费用是x_k加的最高费用的任何节点与边缘x_k.
有一篇论文声称有一个算法:<!>“活动网络中的关键路径,时间约束<!>”;可悲的是,我找不到免费副本的链接。除此之外,我只能提出修改 http://en.wikipedia.org/的想法。 wiki / Dijkstra%27s_algorithm 或 http://en.wikipedia.org/wiki/A *
更新:我为糟糕的格式化道歉<!>#8212;服务器端降价引擎显然已损坏。
我的第一个答案,请原谅堆栈溢出文化中的任何非标准事物。
我认为解决方案很简单。只需否定权重并运行DAG的经典最短路径(当然为顶点权重修改)。它应该运行得相当快。 (O(V + E)的时间复杂度可能)
我认为它应该起作用,当你将否定权重时,最大的一个将变得最小,第二个最小的将是第二小的,依此类推,就好像a > b
然后-a < -b
。然后运行DAG应该足够了,因为它将找到被否定的最小路径的解决方案,从而找到原始路径的最长路径
不隶属于 StackOverflow