首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2012-06-26
84
问题
已知加权有向图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
学硕统考专业
相关试题推荐
确定我国经济体制改革目标的核心问题是正确认识和处理()。
下列不是美国独立战争与美国内战的相同点的是()。
清廷为稳定地方统治,严厉裁抑乡绅权力,连续制造了几起大案,不包括()
林则徐的反英国侵略的策略思想不包括()。
简述隋唐三省六部制的职能与作用。(西北大学2005年中国古代史真题)
毛泽东从事了大量理论研究工作,系统阐述了新民主主义的理论,下列选项中,不属于这一范围的是()
所罗门死后不久,以色列犹太王国遂分裂为北方的以色列王国和南方的犹太王国。后来,两国分别为哪两个国家所灭?()
关于俄国工业革命的特点,正确的是()。①外国资本和技术在工业革命中起着重要的作用②工业革命发展极不平衡③企业资本有机构成低,技术落后④工业革命所需的资金主要来自对海外殖民地的掠夺
光纤分为单模光纤和多模光纤,这两种光纤的区别是()。
如下图所示为一个带宽为50kbps的卫星信道,它的往返传播延时为500ms。现在有一个网络架设在该信道上,网络使用1000bit长度的帧和停止一等待协议,请回答如下问题:(1)该网络发送一帧的发送延时和传输延时分别是多少?(2)网络的利
随机试题
企业在未来的几乎所有活动都可以利用___________进行控制。
穿无菌手术衣和戴无菌手套后,不能接触的有菌地带是
银行履约保函是由商业银行开具的担保证明,通常为合同金额的()左右。银行保函分为有条件的银行保函和无条件的银行保函。
从事生产、经营的纳税人应当自领取营业执照之日起()日内,持有关证件向税务机关申报办理税务登记。
依照增值税的现行规定,下列货物销售,不适用13%增值税税率的是()。
企业采用支付手续费方式委托代销商品,委托方应在发出商品时确认销售商品收入。()
下列各项所得应按“经营所得”项目征税的有()。
学生学习是为了改变自己在班集体中的排名,这样的学习动机属于()。
A、asecuritysignedbytheissuerwhopromisestopayB、asecurityissuedbythecreditorwhoinstructingthedebtortopayC、a
HowmanyancientGreekstatueswereremovedindoors?
最新回复
(
0
)