首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2012-06-26
88
问题
已知加权有向图G如下,回答下列问题:
(1)画出该有向图G的邻接矩阵;
(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
选项
答案
(1)有向图G的邻接矩阵 [*] (2) [*]
解析
本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk-stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是:
(1)设置两个顶点的集合S和T=V—S,集合S中存放已找到最短路径的顶点,集合T存放当前还未找到最短路径的顶点。
(2)初始状态时,集合S中只包含源点v
0
,然后不断从集合T中选取到顶点b>路径长度最短的顶点u加入到集合S中,集合S每加入一个新的顶点u,都要修改顶点b>到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。
(3)此过程不断重复,直到集合T的顶点全部加入到S中为止。
转载请注明原文地址:https://kaotiyun.com/show/3fxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
确定我国经济体制改革目标的核心问题是正确认识和处理()。
清廷为稳定地方统治,严厉裁抑乡绅权力,连续制造了几起大案,不包括()
对《魏玛宪法》的内容和影响叙述不正确的是()。
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为封建社会
对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作用
1988年起,苏联民族矛盾激化,民族分离运动加剧,第一次较大规模的民族冲突是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
假定站点A和B在同一个10Mbit/s以太网的网段上,这两个站点之间的传播时延为225bit时间。现假定A开始发送一帧,并且在A发送结束之前B也发送一帧。如果A发送的是以太网所允许的最短的帧,试问:在(1)中的站点A和B在t=0时同时发送了数据帧。当t
拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。仅从铺设费用角度出发,给出所有可能的最经济的光纤铺设方案(用带权图表示),并计算相应方案的总费
随机试题
女性,26岁,面容改变,手脚变粗大2年,闭经1年余,婚后4年未生育。查体:额头变大,下颌突出,鼻大唇厚,发音变粗,手指变粗,脚肥厚,眼底双侧视神经乳头边清色淡女性,24岁,闭经2年,未婚。查体:精神差,肥胖,圆脸,腹部、大腿皮肤有紫纹,血压偏高
A.路路通B.防己C.千年健D.乌梢蛇E.五加皮治疗风寒湿痹,腰膝冷痛,宜选用
患者,男,20岁,左下腹隐痛伴脓血便2年,加重3个月,诊断为“溃疡性结肠炎”。下列护理措施中错误的是()
甲的行为构成:丙的行为构成:
将女子教育纳入学制并取消读经课和忠君忠孔等内容的学制是()。
根据下面材料回答下列题。2012年1—5月,规模以上轻工企业累计实现工业总产值66933.3亿元,同比增长18。4%:5月份完成工业总产值14777.1亿元,同比增长15.7%。农副食品加工、塑料制品、食品制造、造纸、家电、皮革及制鞋、酿酒、五金、
Therearesigns________Internetarebecomingmoreandmorepopularwithteenagers.
晓雨任职人力资源部门,她需要对企业员工Office应用能力考核报告进行完善和分析。按照如下要求帮助晓雨完成数据处理工作。在考生文件夹下,将“Excel素材.xlsx”文件另存为“Excel.xlsx”(“.xlsx”为扩展名),后续操作均基于此文件,否
打开考生文件夹下的演示文稿yswg.pptx,按照下列要求完成对此文稿的修饰并保存。将第二张幻灯片版式改为“两栏内容”,将第三张幻灯片的图片移到第二张幻灯片右侧内容区,图片动画效果设置为“轮子”,效果选项为“3轮辐图案”。将第三张幻灯片版式改为“
Withoutthefrictionbetweenourfeetandtheground,we(not,be)______abletowalk.
最新回复
(
0
)