首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引入“转弯”的定义如下:在从s旅行到t的过程中,每从一条公路转到另一条公路上时称进行了一次转弯,从城市s到城市t最少经过(56)次转弯。
11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引入“转弯”的定义如下:在从s旅行到t的过程中,每从一条公路转到另一条公路上时称进行了一次转弯,从城市s到城市t最少经过(56)次转弯。
admin
2007-10-11
57
问题
11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引入“转弯”的定义如下:在从s旅行到t的过程中,每从一条公路转到另一条公路上时称进行了一次转弯,从城市s到城市t最少经过(56)次转弯。
选项
A、92
B、82
C、81
D、73
答案
C
解析
本题是一个典型的图论算法的应用问题。既可以看作赋权简单连通无向图的单源问题进行求解,也可以用两结点间最短距离算法进行求解。
采用单源问题的迪克斯特拉(E.W Dijkstra)算法求解。
将题图中未标记的结点进行标记,得到下图:
令S={s},T={a,b,c,d,e,f,S,h,i,t},
D(s)=0,D(a)=25,D(b)=21,D(c)=+∞, D(d)=+∞,D(e)=+∞,D(f)=+∞,
D(g)=+∞, D(h)=+∞, D(i)=+∞, D(t)=+∞。
因为D(b)=21是T中最小的D值,选x=b,令S ←S∪{X}={s,b}。
令T ←T-{X}={a,d,c,d,e,f,g,h,i,t},然后计算:
D(a)=min(25,21+23)=25,D(c)=min(+∞,21+20)=41,D(d)=min(+∞,21+25)=46,
D(e)=min(+∞,+∞)=+∞,D(f)=min(+∞,+∞)=+∞,D(g)=min(+∞,+∞)= +∞,
D(h)=min(+∞,+∞)=+∞,D(i)=min(+∞,+∞)=+∞,D(t)=min(+∞,+∞)= +∞。
如此类推,直到T=
终止,整个过程概括于表如下:
D(t)=81,所以城市s到城市t的最短距离为81。
转载请注明原文地址:https://kaotiyun.com/show/xOQZ777K
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
.什么是code-behind技术
快速排序(东软喜欢考类似的算法填空题,又如堆排序的算法等)
为邮件到达后应用规则“若发件人包含‘mary@sina.com’转发到wangtao@sina.com”。
设置Internet临时文件保存在D:\临时文件\。
通过收藏夹访问新浪新闻中心。
添加新联系人,姓名为:王龙;邮件地址为:wanglong@lnu.edu.cn。
用金山毒霸“创建应急u盘”工具,创建应急u盘。要求不格式化,直接操作,其他数据使用默认值(假如u盘已插入)。
在桌面上新建一个名为LX.TXT的文本文件,内容为"I’mateacher."并将其保存到A盘。
Excel97的工作簿、工作表、单元格的关系是()。A.工作簿由工作表构成,工作表由单元格构成B.工作表由工作簿构成,工作表由单元格构成C.工作簿由工作表构成,工作簿由单元格构成D.工作表由单元格构成,工作簿是工作表的一部分
利用“剪贴板”把桌面上的活动窗口以图片的形式保存在D盘根目录下,并且文件名保存为“对话框.bmp”。
随机试题
心力衰竭时下述减轻心脏负荷的治疗措施中。哪一项是不正确的
对于齿面硬度
应急响应是在事故发生后立即采取的应急与救援行动,其中包括:()。
工程勘察资质分为()。
王老师是中途接手某班的班主任,发现学生畏难情绪大,只要作业题目难一点或量大一点,就不能按时完成作业,而且在集体活动中经常叫苦叫累,如果你是王老师的话,可在全班进行()。
你以前的经验和我们现在的工作有哪些联系?
国家政治保卫局是我国最早的人民政权的公安保卫机关。()
设四阶方阵A满足条件|3E+A|=0,AAT=2E,|A|
Astheconversationbegins,whatarethemanandwomandoing?
Nursing,asatypicallyfemaleprofession,mustdealconstantlywiththefalseimpressionthatnursesaretheretowaitonthep
最新回复
(
0
)