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

admin2013-07-12 60

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

学硕统考专业

规定了电流、电动势、电阻等概念的物理学家是()。

1941年～1942年，中共在根据地建设中，为争取抗战胜利奠定物质基础的措施是()。

19世纪三四十年代无产阶级把反对资产阶级的斗争推进到一个新阶段的根本原因是()。

论述一战后德国的赔款问题

1911年，美国工程师()出版《科学管理原理》一书，奠定了科学管理的理论基础，被誉为“科学管理之父”。

中国第一条自行设计修建的铁路是在()

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

股份有限公司发起人出资的形式可以是

简述边际替代率递减规律。

滑动性疝系指

对医师的业务水平、工作成绩和职业道德状况，依法享有定期考核权的单位是

A、异戊二烯B、焦磷酸γγ-二甲基丙烯酯C、甲戊二羟酸D、异戊二烯聚合物E、葡萄糖萜类化合物的骨架是

根据《房屋登记办法》，可以办理房屋预告登记的情形有()。

金融租赁公司是以经营融资租赁业务为主的非银行金融机构。在租期内，承租人对租赁设备()。

许多道教宫观以“太清官”“上清宫”命名，“太清”和“上清”分别是()。

公安机关在边防检查工作中，有权对出入境口岸过境人员、交通工具实施检查、监护，但无权对违章违法事件与案件进行查处。()

HighfuelpriceswillprobablykeepAmericansclosertohomethissummer.ArecentpollbyAOLandZogbyfoundthat30%ofAmeri