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

admin2019-08-15 85

问题对于如下的加权有向图，给出算法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

学硕统考专业

相关试题推荐

鸦片战争失败后，西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点，对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答问题:西方列强在近代中国攫取的第一块殖民地和第一个租界是()
赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：为了限制三帅的权力过大，宋代在中央设立()机构，主管全国的军队调动、训练、供给等事宜。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一，为重新认识三代的历史与文化奠定了基础，开辟了坦途，可称之为中国文化史的里程碑。根据所学知识回答问题：在甲骨文的研究流域，对甲骨文研究作出了重大贡献，被后人称为“甲骨四堂”的四位学者是(
唐朝时期，每丁服徭役二十天，是为正役，国家若不需要其服役，则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准，交足二十天的数额以代役，称为()。
试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡H同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点，链表结点结构为请设计一个时间上尽可能高效的算法，找出

随机试题

四边孔
1950年6月，中国共产党为争取国家财政经济状况的基本好转而召开的重要会议是()
下列属于输出设备的是_______。
在夏季施用有机磷农药，出现中毒症状，在急诊室进行处理时，首选措施是
下列属于单位工程投入使用验收工作内容的是()。
银行存款余额调节表中，银行对账单余额应减去企业已收银行未收。()
值班备勤是要求各级公安机关在任何时候、任何情况下，始终处于常备不懈的戒备状态，坚守岗位，履行职责，按时交接班，保持公安工作的连续性、有序性，维护良好的社会秩序。()
结合材料回答问题：材料1习见平强调，“一带一路”建设是我国在新的历史条件下实行全方位对外开放的重大举措、推行互利互赢的重要平台。我们必须以更高的站位、更广的视野，在吸取和借鉴历史经验的基础上，以创新的理念和创新的思维，扎扎实实做好各项工作使沿线各国人民
设D：χ2＋y2≤R2，则＝_______．
将数据库的结构划分成多个层次，是为了提高数据库的逻辑独立性和

最新回复(0)

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

计算机408

学硕统考专业

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：为了限制三帅的权力过大，宋代在中央设立()机构，主管全国的军队调动、训练、供给等事宜。

唐朝时期，每丁服徭役二十天，是为正役，国家若不需要其服役，则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准，交足二十天的数额以代役，称为()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。

四边孔

1950年6月，中国共产党为争取国家财政经济状况的基本好转而召开的重要会议是()

下列属于输出设备的是_______。

在夏季施用有机磷农药，出现中毒症状，在急诊室进行处理时，首选措施是

下列属于单位工程投入使用验收工作内容的是()。

银行存款余额调节表中，银行对账单余额应减去企业已收银行未收。()

值班备勤是要求各级公安机关在任何时候、任何情况下，始终处于常备不懈的戒备状态，坚守岗位，履行职责，按时交接班，保持公安工作的连续性、有序性，维护良好的社会秩序。()

设D：χ2＋y2≤R2，则＝_______．

将数据库的结构划分成多个层次，是为了提高数据库的逻辑独立性和