首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引入“转弯”的定义如下:在从s旅行到t的过程中,每从一条公路转到另一条公路上时称进行了一次转弯,从城市s到城市t最少经过(56)次转弯。
11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55) ;现引入“转弯”的定义如下:在从s旅行到t的过程中,每从一条公路转到另一条公路上时称进行了一次转弯,从城市s到城市t最少经过(56)次转弯。
admin
2007-10-11
55
问题
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
系统分析师上午综合知识考试
软考高级
相关试题推荐
两个单向链表,找出它们的第一个公共结点。链表的结点定义为:structListNode{intm_nKey;ListNode*m_pNext;};
定义Fibonacci数列如下:输入n,用最快的方法求该数列的第n项。
设置拨号连接属性卸载Qos数据包计划程序。
通过收藏夹访问新浪新闻中心。
在MSN即时通讯工具中,将首发消息时显示的图片设置为D:\picture\picturel.jpg。
设置在当前界面中显示队列状态栏,并在队列状态栏中显示合计文件的大小。
在当前窗口界面中,根据“添加打印机”向导,安装网络打印机,输入名称为“\\192.168.18.18\MicrosoftXPSDocumentWriter”。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
在Excel97中,工作薄窗口冻结的形式包括()。A.水平冻结B.垂直冻结C.水平、垂直同时冻结D.以上全部
关于层和表格的关系,以下说法正确的是______。A.表格和层可以互相转换B.表格可以转换成层C.只有不与其它层交叠的层才可以转换成表格D.表格和层不能互相转换
随机试题
“阴在内,阳之守也;阳在外,阴之使也”说明了阴阳之间的哪种关系
A.25周B.28周C.30周D.35周E.40周羊水内肺表面活性物质迅速增加的时间是
工程项目管理层次不包括()。
钢筋下料后应按()分别挂牌标明。
会计核算软件应具备的初始化功能包括()。
提出“在集体中进行教育”的原则和方法的教育家是()。
2,12,36,80,()
下列心理学流派对知觉组织的心理过程提出了系统的理论解释的是()
PromisingResultsfromCancerStudyAnewexperimentalvaccine(疫苗)hasshownpromisingresultsinthefightagainstlungcanc
Whereisthemangoingonvacation?
最新回复
(
0
)