首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2012-06-26
89
问题
已知加权有向图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
学硕统考专业
相关试题推荐
明清时期的文化科技特征不包括()。
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
试论述清朝前期是如何巩固统一的多民族国家的?
南宋理学家()认为一切封建秩序和伦理纲常都是人“本心”所固有的,而不是来自朱熹等人所说的“天理”。他的这一学说被称为“心学”。
下列事件中,不是发生在上海的是()
下列不是战国时代魏国李悝变法的内容的是()
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
光纤分为单模光纤和多模光纤,这两种光纤的区别是()。
随机试题
TheRedCrossis【B1】______organizationwhichcaresforpeoplewhoarein【B2】______ofhelp.AmaninaParishospitalwhonee
资产评估中,某项资产的最大最优用途是指()。
近年来.我国在国际事务中发挥着越来越重要的作用。多边外交力度明显加大。我国对外交往的根本准则是()。
对精神病人应当采取约束。()
孔子特别强调做事情的分寸,“过”和“不及”都是要尽力避免的。孔子提倡仁爱,但他并不认为应当以丧失原则的仁爱之心宽宥所有人的过失。有人问他:“以德报怨,何如?”孔子的回答是:“以直报怨,以德报德。”与这段文字文意不相符的是()。
下列属于互动式的支架的是()。
[*]
以下说法中正确的是( )。
Accordingtoonespeaker,wecouldskip______ifweareshortoftime.
Theageofrequiringretirementincompaniesshouldberaised,andso【M1】______shouldtheagetobeginSocialSecurity.First
最新回复
(
0
)