搜索
编程论坛 → 开发语言 → 『 数据结构与算法 』 → 计算所有点对最短路径，神马算法最高效？
标题：计算所有点对最短路径，神马算法最高效？
只看楼主
ronan_ly
Rank: 1
等　级：新手上路
帖　子：2
专家分：0
注　册：2011-3-8
结帖率：0
楼主
 已结贴√  问题点数：20 回复次数：5 
计算所有点对最短路径，神马算法最高效？
已知一个图是完全图，在计算所有点对的最短路径问题中，采用什么算法比较高效
Dijkstra算法肯定不是最高效的
动态规划？ 还是采用A*算法？或者其他算法？
A*算法需要指定起始点和终点，算法完成后，得到一对节点间的最短路径。如果要计算所有点对间的最短路径，A*算法要怎么操作（难道要用枚举？）

还有就是采用动态规划的方法时，如何保存最短的路径？（算法最后应该输出点对之间的最短路径）
搜索更多相关主题的帖子: 神马　
2011-03-08 17:02
卧龙孔明
Rank: 9Rank: 9Rank: 9
等　级：贵宾
威　望：59
帖　子：3872
专家分：684
注　册：2006-10-13
第 2 楼
 得分:7 
floyed

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-03-08 17:05
ronan_ly
Rank: 1
等　级：新手上路
帖　子：2
专家分：0
注　册：2011-3-8
第 3 楼
 得分:0 
以下是引用卧龙孔明在2011-3-8 17:05:07的发言：

floyed
貌似floyed与动态规划的方法没有本质的区别？都是O(N^3)

[ 本帖最后由 ronan_ly 于 2011-3-8 17:15 编辑 ]
2011-03-08 17:11
诸葛修勤
Rank: 10Rank: 10Rank: 10
等　级：贵宾
威　望：11
帖　子：549
专家分：1955
注　册：2010-10-28
第 4 楼
 得分:7 
图啊。。。
2011-03-08 18:15
卧龙孔明
Rank: 9Rank: 9Rank: 9
等　级：贵宾
威　望：59
帖　子：3872
专家分：684
注　册：2006-10-13
第 5 楼
 得分:0 
以下是引用ronan_ly在2011-3-8 17:11:10的发言：

貌似floyed与动态规划的方法没有本质的区别？都是O(N^3)


floyed就是dp

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-03-08 18:24
草狼
Rank: 9Rank: 9Rank: 9
等　级：蜘蛛侠
威　望：2
帖　子：577
专家分：1040
注　册：2010-4-6
第 6 楼
 得分:7 
能否用LCA算法在O（n+n^2）做呢  只是猜想
2011-03-09 16:06



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-333574-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.021019 second(s), 7 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved