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

admin2013-07-12 45

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

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

选项

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

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

利玛窦与李之藻合译的()一书，介绍了西方数学中的算术知识，尤为可贵的是，其传入了中国所没有的西洋笔算法。

当代科技革命使社会经济结构发生深刻变化，这表现在()。

下列各项不是“南北议和”形成的原因的是()。

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

以下不属于国民党控制金融的“四行”的是()。

简述马克思主义在中国传播的本土化特点。

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

下列诗作中，抒写新时期青年爱国深情的是()

以下关于缺陷责任期的说法，正确的是()。

《最高人民法院关于审理建设工程施工合同纠纷案件适用法律问题的解释》规定，发包人()，致使承包人无法施工，且在催告的合理期限内仍未履行相应义务，承包人请求解除建设工程施工合同的，应予支持。

(2008年考试真题)下列关于分公司法律地位的中，正确的有()。

下列有关财务管理目标的表述中，正确的是()。

班级越大，内部越容易形成各种非正式小群体。()

对关系S和R进行集合运算，结果中既包含S中的所有元组也包含尺中的所有元组，这样的集合运算称为()。

HowPovertyChangestheBrainA)Yousawthepicturesinscienceclass—aprofileviewofthehumanbrain,sectionedbyfuncti