首页 > 试题广场 >

给定一个如下所示的图，图中的边代表了两个节点间的距离。如

[单选题]

给定一个如下所示的图，图中的边代表了两个节点间的距离。如果使用迪杰斯特拉算法对节点 1 和节点 8 求最短路径，则当完成计算时，算得节点 1 到节点 8 的最短路径是？同时当完成节点 1 到节点 8 的最短路径计算时，节点 1 到哪些节点（除了 1 和 8 ）的最短路径也已经计算完毕？（　） 


  • 最短路径：７；已经算得最短路的节点：３，５，６
  • 最短路径：４；已经算得最短路的节点：５
  • 最短路径：４；已经算得最短路的节点：２，３，５，４
  • 最短路径：４；已经算得最短路的节点：５，６
查看正确选项
添加回答
捧碗头像 捧碗
由迪杰特斯拉算法的步骤可以得出d[ ]变化为： ｛1｝ ｛1，5｝ ｛1，5，3｝ ｛1，5，3，2｝ ｛1，5，3，2，4｝ ｛1，5，3，2，4，8｝
发表于 2018-04-12 17:22:09 回复(0)
Payaso_hah头像 Payaso_hah
我服气，上一次遇到这个题我选C结果正确答案是B,说是有同时两个字，我还觉着挺有道理的，这次一模一样的题我吃一堑长一智选了B现在你又告诉我选C？  逗我玩呢？
发表于 2017-08-08 13:55:24 回复(1)
学不会的IT小渣头像 学不会的IT小渣
初始状态：路径长度0：（1）
路径长度1：（1,5）
路径长度2：（1,3）
路径长度3：（1,3,4），（1,2）
路径长度4：（1,5,8）
节点1到8的最短路径长度为4；     2，3,4,5节点的最短路径已经计算完毕；   其中到5节点的最短路径最小为1；
应该选C，感觉出题人玩文字游戏把自己绕进去了
编辑于 2017-07-22 10:54:56 回复(6)
0_0?头像 0_0?
Dijkstra是一种用来求单源最短路径的算法。
单源是什么意思？
  • 从一个顶点出发，Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。
算法思想：
  • 维护一个集合 S，集合内的点是已经确定最短路径的结点；
  • 每次操作找出与集合相邻的点中距离起点最近的结点加入集合中，并确定它的最短路径值为它的前一已确定结点的最短路径值+该边权值，存在dis数组中。
算法流程：
  • 首先把结点1加入集合（红色结点），蓝色结点为相邻结点， s={1}，dis[]={0,∞,∞,∞,∞,∞,∞,∞}
  • 与S相邻的结点为2、3、5，把相邻结点路径最短的加入集合（即结点5） s={1,5}，dis[]={0,1,∞,∞,∞,∞,∞,∞}
  • 与S相邻的结点为2、3、6、8，把相邻结点路径最短的加入集合（即结点3） s={1,5,3}，dis[]={0,1,2,∞,∞,∞,∞,∞}
  • 与S相邻的结点为2、4、6、8，把相邻结点路径最短的加入集合（即结点2和4） s={1,5,3,2,4}，dis[]={0,1,2,3,3,∞,∞,∞}
  • 与S相邻的结点为6、7、8，把相邻结点路径最短的加入集合（即结点8） s={1,5,3,2,4,8}，dis[]={0,1,2,3,3,4,∞,∞}
  • 与S相邻的结点为6、7，把相邻结点路径最短的加入集合（即结点6和7） s={1,5,3,2,4,8,6,7}，dis[]={0,1,2,3,3,4,5,5}
发表于 2021-10-30 20:06:18 回复(0)
跪求靠谱offer头像 跪求靠谱offer
2,3,4,5,6都求出了最短把

发表于 2017-08-17 22:08:26 回复(0)
matthewC头像 matthewC
设集合S为已求出最短路径的集合，U为未确定最短路径的顶点集合 对上图进行dijkstra算法
step1: (其中括号里面的数值为当前最短路径的长度)
S:①(0) 
U:②，③，④，⑤，⑥，⑦，⑧
step2:
S:① (0)，⑤(3)
U:②，③，④，⑥，⑦，⑧
step3:
S:① (0)，⑤(3)，⑧(4)
U:②，③，④，⑥，⑦
step4:
S:① (0)，⑤(3)，⑧(4)，⑥(6)
U:②，③，④，⑦
step5:
S:① (0)，⑤(3)，⑧(4)，⑥(6)，⑦(8)
U:②，③，④
step6:
S:① (0)，⑤(3)，⑧(4)，⑥(6)，⑦(8),②(3)
U:③，④
step7:
S:① (0)，⑤(3)，⑧(4)，⑥(6)，⑦(8)，②(3)，③(2)
U:④
step8:
S:① (0)，⑤(3)，⑧(4)，⑥(6)，⑦(8)，②(3)，③(2)，④(3)
U:空

发表于 2017-02-21 21:21:48 回复(0)
脚踩黄金切尔西头像 脚踩黄金切尔西
第一步1-5
第二步1-3
第三步1-2
第四步1-3-4
第五步1-5-8
发表于 2020-10-29 21:44:31 回复(0)
哇咔哇咔头像 哇咔哇咔
题目答案是对的。具体如下：








发表于 2017-08-06 17:26:04 回复(0)
傻梨吃渣梨头像 傻梨吃渣梨
因为1到8的最短路径是4，所以所有最短路径小于4的都已经被计算完毕！
发表于 2021-06-03 09:31:29 回复(0)
直上云霄头像 直上云霄
考了语文理解能力 哪些点的最短路径已经算好了 是这个意思
发表于 2019-09-27 13:44:44 回复(0)
四川省学术和技术带头人头像 四川省学术和技术带头人
迪杰斯特拉算法又忘了

发表于 2019-07-12 16:19:55 回复(0)
Happiness_Yu头像 Happiness_Yu
求最短路径，图不应该是有向图吗？怎么无向图也可以求最短路径呢？
发表于 2018-10-13 15:57:08 回复(1)
Forrest_Lin头像 Forrest_Lin
4和7之间的距离为啥没计算呢？计算了4和7之间的距离才能知道从6到8这条路不是最短的吧？
发表于 2018-04-25 17:34:08 回复(0)
辛德瑞拉是好宝宝头像 辛德瑞拉是好宝宝
不理解
发表于 2017-10-01 10:25:41 回复(0)
看见🐳头像 看见🐳
我觉得都不对的，要算完才知道正确的最小值，假如5-6是1，6-8是1。那最小值就是3啦。所以现在不能确定最短路径。
发表于 2017-08-22 18:46:37 回复(0)
像我这样的人啊头像 像我这样的人啊
第街死特拉的，全貌
发表于 2017-08-05 21:59:34 回复(0)
羞香月色头像 羞香月色
题中所求为1到8最短路径计算时，哪些节点的最短路径已经计算完毕。与节点8相连的节点只有5和6，所以应该选节点1到节点5和6的最短距离加上各自到节点8的最小值（所以最短路径可能经过5，也可能经过6）才能得到最短路径（得到动态规划的递推关系）。但是根据本题的实际情况得到的最短路径为1-5 -8，所以应该只与节点5有关。
编辑于 2017-08-04 15:47:24 回复(0)
桀骜猴子头像 桀骜猴子
我不太明白，在确定1->5->8（4）之前，不是先可以确定1->2（3）和1->3（2）的最短路径吗？
编辑于 2017-07-06 10:22:03 回复(0)
Sssssss头像 Sssssss
B
{1}
{1，5}
{1，5，8}


编辑于 2017-08-08 10:55:10 回复(0)
提交观点

问题信息

图
来自：字节跳动2017秋招开...
上传者：牛100
难度：
19条回答 6838浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号