以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  求k最短路算法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=36540)

--  作者：fongzl
--  发布时间：8/8/2006 4:20:00 PM

--  求k最短路算法
急用k最短路算法，我的问题相对比较简单：
无向图，允许环路，允许重复路段

查了几篇论文，也知道了两种算法：
1.删除路段（或节点）法
2.合理前趋法
但是这两种方法我总认为都不对，因为他们都是第n短路来计算第n+1短路，我认为这样不一定可以找到，因为第n+1短路可能只能根据前面的某条最短路计算，而无法根据第n短路计算。

--  作者：shiyr
--  发布时间：8/8/2006 4:46:00 PM

--  
写偏离算法吧 ...
--  作者：Logician
--  发布时间：8/8/2006 10:51:00 PM

--  
什么是“允许重复路段”？
是说允许输入的图中有重边？还是说允许找出的“k最短路”中多次通过同一条边？
另外，“k最短路”是说“输入：一个带权图W，图中的两个顶点a,b，以及正整数k。输出：从a到b的，长度为第k短的通路。”是这样吗？
--  作者：fongzl
--  发布时间：9/13/2006 11:31:00 AM

--  
就是允许有重复边了
要找出路网中所有点之间的k条最短路

有人有算法吗？

--  作者：fongzl
--  发布时间：10/23/2006 2:29:00 PM

--  
大家帮帮忙阿
--  作者：beesharp
--  发布时间：10/25/2006 3:43:00 PM

--  
求的所有点对的第K条最短路啊?
还真要仔细想想了,楼主对这个算法有什么应用?
--  作者：xunemg_7
--  发布时间：11/25/2006 2:00:00 PM

--  
找出两点间的k条最短路是NP-C的
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 62.500ms