首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2012-06-26
103
问题
已知加权有向图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
学硕统考专业
相关试题推荐
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
在巴黎和会上获利最大的两个国家是()。
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
巴黎和会讨论的中心问题是()。
论述1931—1941年英美远东政策的变化及对中国的影响。(2014年统考真题)
分析英、法、美三国资产阶级革命的特点。
下列不是美国独立战争与美国内战的相同点的是()。
解析两个战场的地位、作用及相互关系。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
随机试题
关于影响钢筋混凝土梁斜截面抗剪承载力的主要因素,错误的是()。
如图7-39所示电路中电压u含有基波和三次谐波,基波角频率为104rad/s。若要求u1中不含基波分量而将u中的三次谐波分量全部取出,则C1应为()μF。
下列关于热风炉由燃烧转为送风的换炉操作程序,排序正确的是()。
施工项目一旦发生安全事故,必须实施“四不放过”的原则,包括()。
付款凭证左上角的“贷方科目”可能登记的科目有()。
下列哪一选项与其他三个选项使用的修辞手法不一致?()
表中所列各大洲中(除亚洲外),投产企业占实有三资企业比重超过2/3的有()个。
2018年12月8日,“嫦娥四号”探测器在西昌卫星发射中心成功发射。下列关于“嫦娥四号”的说法不正确的是:()
2008年到2012年间,该市文化产业总值增长最快的年份是()。
Ifthefunctiongisdefinedforallnonzeronumbersybyg(y)=,findthevalueofeachofthefollowing.(a)g(2)(b)g(-2)(c)g
最新回复
(
0
)