已知加权有向图G如下，回答下列问题： (1)画出该有向图G的邻接矩阵； (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

admin2012-06-26 92

问题已知加权有向图G如下，回答下列问题：

(1)画出该有向图G的邻接矩阵；
(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

选项

答案(1)有向图G的邻接矩阵 [*] (2) [*]

解析本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk-stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是：
(1)设置两个顶点的集合S和T=V—S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。
(2)初始状态时，集合S中只包含源点v₀，然后不断从集合T中选取到顶点b>路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点b>到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。
(3)此过程不断重复，直到集合T的顶点全部加入到S中为止。

转载请注明原文地址:https://kaotiyun.com/show/3fxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

已知加权有向图G如下，回答下列问题： (1)画出该有向图G的邻接矩阵； (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

计算机408

学硕统考专业

康熙五十九年(1720)指定()组织“公行”(“十三行”)专营对外贸易。凡外商税项的征收、货物的交易，以及外商生活的管理等，均归“行商”负责。

建国初期，为稳定社会秩序和恢复经济，人民政府最迫切需要解决的问题是()。

下列内容，哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张，从经济上瓜分世界

东汉时期，在宫廷朝见中所谓的“三独坐”，其中不包括()

下列不属于清统治者加强文化专制和思想控制的是()

论述西晋占田制的实行及其意义。(兰州大学2001年中国古代史真题；北京师范大学2004年历史学综合真题)

论述魏晋玄学。

CRT显示器显示图形图像的原理是图形图像()。

教会法

判断小儿体格发育是否正常最主要的指标是

宋某、周某、李某、王某在2001年改制时所取得的股权是否有效?为什么?()。蓝某可否根据补偿协议获得王某所持股权的50%?为什么?()。

()同称为欧洲古典建筑。

空调系统带冷(热)源的正常联合试运转，不应少于（）小时，当竣工季节与设计条件相差较大时，例如夏季可仅作带冷源的试运转，冬期可仅作带热源的试运转。

该批货物的保税额度是()。乐友公司对该批货物应付保证金的情况为()。

两种正相关的股票组成的证券组合，不能抵消任何风险。()

在下列财务风险与经营风险的搭配中，可以同时符合权益投资人和债权投资人期望的有()。

A、 B、 C、 D、 D给图像是由f(x)=ax的图像左移得到的，故b

(2001年)设生产函数为Q=ALαKβ，其中Q是产出量，L是劳动投入量，K是资本投入量，而A，α，β均为大于零的参数，则当Q=1时K关于L的弹性为_______。