笔试题:最短路径问题

请选出在附图上运行最短路径算法时,可能会依次添加到已选集合的边的顺序。
A. CE,AD,BE,DF,AB,EG 
B. AD,CE,DF,BE,AB,EG 
C. AD,DF,CE,AB,BE,EG 
D. EG,CE,BE,AB,AD,DF 
试了Dijkstra算法,google,不知道选哪个答案
全部评论
求别毁三观!虽然我不知道选啥,但是你们也别拿别的算法乱凑好么
点赞 回复 分享
发布于 2016-09-10 18:26
最短路径和最小生成树有什么联系吗?看到一些文章把无向图的最小生成树看作是最短路径
点赞 回复 分享
发布于 2016-09-10 16:04
Kruskal算法,即按照边的权值进行从小到大的排序,每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的边,加入到生成树中,直到加入了n-1条边。则选择B Prim算法:选择任意一个顶点加入生成树,找出一条边添加到生成树,枚举每一个树顶点到每一个非树顶点所有的边,然后找到最短边加入生成树,重复此步骤知道添加全部顶点。则选D
点赞 回复 分享
发布于 2016-09-10 15:42
B= =
点赞 回复 分享
发布于 2016-09-10 14:27
貌似最短路径都不对啊。不过如果是最小生成树,prim应该选D
点赞 回复 分享
发布于 2016-09-10 14:13
试一下经典的最小生成树算法
点赞 回复 分享
发布于 2016-09-10 14:08

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务