论坛 › 图论算法 › 关键路径问题~~~求高手

comey 发表于 2011-8-11 09:11

关键路径问题~~~求高手

有谁研究过带环的有向图的关键路径啊？请教请教，指点指点小菜

黑照 发表于 2011-8-11 21:03

关键路径问题就是最大路径。你直接找个比最大路径都大的值。比如255.然后全部减去一下。就变成了求最小路径。最小路径所在的路径就是关键路径。当然一个图中可能不止一个关键路径。比如正方形的两个端点。
至于有没有环都无所谓。用矩阵迭代，Dijkstra,还有弗洛伊得算法都可以。算出来。
有环不是坏事。只要不是负权值的环就可以了。

comey 发表于 2011-8-16 16:31

大侠。。。。能提供点思路吗？

alair005 发表于 2012-2-7 11:43

redeom 发表于 2012-3-19 08:00

什么是关键路径？

查看完整版本: 关键路径问题~~~求高手