查看: 4620|回复: 4

[问题求助] 关键路径问题~~~求高手

字体大小: 正常放大

comey

1 主题	3 听众	20 积分

升级 15.79%

TA的每日心情

	无聊 2011-9-13 12:06

签到天数: 1 天

[LV.1]初来乍到

自我介绍: 物

电梯直达

1^#

发表于 2011-8-11 09:11 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

zan

转播0 淘帖0 分享0 收藏0 支持1 反对0 微信

使用道具举报

黑照

0 主题	0 听众	3 积分

升级 60%

该用户从未签到

2^#

发表于 2011-8-11 21:03 |只看该作者 |招呼Ta 关注Ta

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