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

admin2013-07-12 22

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

学硕统考专业

简述鸦片战争的三个阶段。

共产国际“七大”决定加强各国共产党的自主性，主要是由于()。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

在中国共产党的“西部大开发”战略中，提出要依托亚欧大陆桥、长江水道、西南出海通道等交通干线，逐步形成一些有特色的跨行政区域的经济带，以下不属于其中的是()

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

改革开放以来，乡镇企业的异军突起，其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径

1543年，发表了解剖学专著《人体结构》的是()。

一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时，最后一个IP分片的数据长度是()。

Thepopulationofourcityisaboutthreetimesaslargeas________oftheirs.

A、末梢神经炎B、听力障碍C、视神经炎D、肝功能损害E、胃肠道不适链霉素的主要不良反应是（）

法洛四联征不包括下列哪一种畸形

在会计电算化信息系统的开发与应用中，()是电算化系统的应用阶段。

某甲对A市B区公安分局管辖的一派出所作出的罚款30元的处罚决定不服。若某甲提出行政复议，他应向哪个机关申请?()

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

公安机关的督察机构对人民警察的执法活动进行现场督察，这种形式的监督称为事中监督。（）

TheXinhuabookstorechain,China’slargestofficialpublishingenterprise,hasbecomeasurprisingflashpointforinterestamo

指令系统是否精简的问题上，产生了两大类计算机系统，它们的英文缩写分别是CISC和_____。

Doctorsbelievethatsecond-handsmokemaycauselungcancerinpeoplewhodonotsmoke.Nonsmokersoftenbreatheinthesmokef