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

admin2012-06-26 73

问题已知加权有向图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

学硕统考专业

明清时期的文化科技特征不包括()。

邓小平在同江泽民等谈话时提出的中国社会主义农业改革和发展的“两个飞跃”是()。

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车

以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍

德国法西斯能够通过合法方式夺取政权，主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党

以下关于玛雅文明叙述，不正确的是()。

林则徐的反英国侵略的策略思想不包括()。

简述隋唐三省六部制的职能与作用。(西北大学2005年中国古代史真题)

俄罗斯的私有化进程始于()年。

企业的双重身份是“经济人”和()

治疗癫痫复杂部分发作最有效的药物是

根据《招标投标法》的有关规定，评标委员会成员应当客观、公正地履行职务，遵守职业道德，对所提出的评审意见承担()。

在海关注册登记后，可以接受其他单位委托，从事代理报关业务的单位有()。

公司人力资源部门制定未来几年的人力资源规划时应当首先从了解()人手。

在Word的编辑状态下，当前输入的文字显示在()。

在夏文化的探索中，()最具有代表性。

设Ω是由x2+y2=4与围成的空间区域，则

Educationofexceptionalchildrenmeansprovisionofspecialeducationalservicestothosechildrenwhoareeitherhandicappedo