对于如下的加权有向图，给出算法Dijkstra，产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。

admin2019-08-15 79

问题对于如下的加权有向图，给出算法Dijkstra，产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。

选项

答案顶点A到顶点B、C、D、E的最短路径依次是3、18、38、43，按Dijkstra所选顶点过程是B、C、D、E。支撑树的边集合为{＜A，B＞，＜B，C＞，＜C，D＞，＜B，E＞}，具体分析如下表所示。 [*] 提示：此题考查的知识点是最短路径。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100
设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。
如下图所示为一个网络连接的示意图，主机1到主机2采用了SLIP网络连接，SLIP网络可以传输的最大数据段是296字节，主机2和主机3使用了以太网连接。请问：(1)为了使IP不分片，主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。
—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。
设一段正文由字符集{A，B，C，D，E，F)中的字母组成，这6个字母在正文中出现的次数分别为{12，18，26，6，4，34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字
设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

随机试题

一国政府对本国居民或公民纳税人征税时，对其中来源于外国的部分，优先考虑有关国家行使地域管辖权对此已征税的事实，允许这部分所得免征或减征本国税收，该原则称为()
下列关于间质性肺炎描述错误的是
男性，29岁。转移性右下腹痛伴发热36h入院，诊断为急性阑尾炎。入院后腹痛加重，伴有寒战，体温40℃，巩膜轻度黄染，剑突下压痛，右下腹肌紧张，右下腹明显压痛、反跳痛，最可能的诊断是
某工程项目，建设单位与施工单位按照《建设工程施工合同(示范文本)》签订了施工合同。合同工期为9个月，合同总价为840万元。项目监理机构批准的施工进度计划如图1所示(时间单位：月)，各项工作均按照最早时间安排且匀速施工，施工单位的部分报价见表6。施工合同中约
下列关于原料场站的技术要求，说法错误的是()。
不能属于城市内客运交通的是：
某大型企业受金融危机的影响效益出现下滑、负债率偏高。为支持该企业渡过难关，商业银行可以对该企业个别经营指标进行微调并继续将其评定为AAA级客户。()
投资基金的优势是()。
在考生文件夹下存在一个数据库文件“samp3．accdb”，里面已经设计了表对象“tEmp”、窗体对象“fEmp”、宏对象“mEmp”和报表对象“rEmp”。同时，给出窗体对象“fEmp”的“加载”事件和“预览”及“打印”两个命令按钮的单击事件代码，试按以
PleasemakeallcheckspayabletoTheGlassHouse.Toreportanyproblem,contactthesalesrepresentativewhotookyourorderb

最新回复(0)

对于如下的加权有向图，给出算法Dijkstra，产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。

计算机408

学硕统考专业

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

A、1243B、4312C、2134D、3214D图的BFS遍历。D选项，首先访问结点3，与3邻接的结点4、2都未曾访问过，故3后面因该为2、4(或4、2)，故D错。

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中：P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

一国政府对本国居民或公民纳税人征税时，对其中来源于外国的部分，优先考虑有关国家行使地域管辖权对此已征税的事实，允许这部分所得免征或减征本国税收，该原则称为()

下列关于间质性肺炎描述错误的是

男性，29岁。转移性右下腹痛伴发热36h入院，诊断为急性阑尾炎。入院后腹痛加重，伴有寒战，体温40℃，巩膜轻度黄染，剑突下压痛，右下腹肌紧张，右下腹明显压痛、反跳痛，最可能的诊断是

下列关于原料场站的技术要求，说法错误的是()。

不能属于城市内客运交通的是：

某大型企业受金融危机的影响效益出现下滑、负债率偏高。为支持该企业渡过难关，商业银行可以对该企业个别经营指标进行微调并继续将其评定为AAA级客户。()

投资基金的优势是()。

PleasemakeallcheckspayabletoTheGlassHouse.Toreportanyproblem,contactthesalesrepresentativewhotookyourorderb