首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2013-07-12
42
问题
已知加权有向图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中选取到顶点v
0
路径长度最短的顶点“加入到集合S中,集合S每加入一个新的顶点“,都要修改顶点v
0
到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上“到该顶点的路径长度值中的较小值。
(3)此过程不断重复,直到集合T的顶点全部加入到S中为止。
转载请注明原文地址:https://kaotiyun.com/show/Srxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1949年6月,毛泽东发表了系统阐明中国共产党关于建立新中国主张的()。
共产国际“七大”决定加强各国共产党的自主性,主要是由于()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
俄罗斯的私有化进程始于()年。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
解析两个战场的地位、作用及相互关系。
1934年9月苏联加入国联,对此说法错误的一项是()。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
随机试题
担保设立的过程包含()两个阶段。
把下面的句子翻译成现代汉语民为贵,社稷次之,君为轻。
A、Hecansaveonlivingexpenses.B、Heconsiderscookingcreative.C、Hecanenjoyhealthierfood.D、Hethinkstake-awayistaste
女,5岁,发热,2周,轻咳,精神差,一直抗生素静脉治疗,仍发热。近2日诉头痛,时有呕吐,突起抽搐,经用止痉剂、脱水剂好转后仍有间断抽搐,为明确诊断,首要的检查是
A.寒邪客胃证B.饮食伤胃证C.肝气犯胃证D.湿热中阻证E.瘀血停胃证胃脘胀痛,痛连两胁,遇烦恼则痛作或痛甚,嗳气、矢气则痛舒,胸闷嗳气,喜长叹息,大便不畅,舌苔多薄白,脉弦。证属
据《国务院关于加强环境保护重点工作的意见》,对()实行化学需氧量和氨氮排放总量控制。
在我国实际工作中,为了管理和研究方面的需要,通常按资产形态可将投资分为()。
编制人工定额时,工人工作必需消耗的时间包括()。
解决进程同步与互斥问题时,对信号量进行P原语操作是在下列哪类代码区完成的?()
WhatdoesAlexWinstonthinkofherage?
最新回复
(
0
)