|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- [求助]最短路问题！ (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=35481) |
|
-- 作者：sdtangwei -- 发布时间：7/11/2006 10:46:00 AM -- [求助]最短路问题！ 在一个图中如何求得从源点到目的节点即：固定的S-->D的前N短的路径。考虑了好久，还是没实现。要应用DIJKSTRA算法。时间复杂度要低。谢谢！算法中最好带有注释。 |
|
-- 作者：phoenixinter -- 发布时间：7/11/2006 7:09:00 PM -- 前K最短路径是个比较复杂的问题 如果路径中的节点可以重复的话那么可以变形Dijkstra |
|
-- 作者：hezelin -- 发布时间：7/12/2006 10:01:00 PM -- DIJKSTRA,我觉得首先算出一个最短路,且记录一下路径,然后尝试删边,然后再次算出来就好了啊..... 不知道对不对啊?DIJKSTRA可以用费波那切堆优化一下,复杂度是NLOGN的,我能想到的就是这个
|
|
-- 作者：phoenixinter -- 发布时间：7/13/2006 12:05:00 PM -- oh my god Fibonacci Heap... |
|
-- 作者：sdtangwei -- 发布时间：7/13/2006 6:34:00 PM -- 有谁能说得具体点阿，谢了 |
|
-- 作者：fongzl -- 发布时间：8/8/2006 4:24:00 PM --
说具体点阿，我正要找这个算法呢 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |