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

admin2013-07-12 33

问题已知加权有向图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://jikaoti.com/ti/CVajFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

西汉时期最后写定的()一书，包括《素问》与《灵枢》(或称《针经》)两部分，是中国最早的一部医书。

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

国民政府统治确立后，中国社会仍存在革命条件并成为唯一选择的主要原因是()。

简评斯大林《苏联社会主义经济问题》。

两次德国统一的历史条件比较

下列关于第三次科技革命的说法，不正确的是()。

【萧规曹随】华东师范大学2003年中国古代史真题；南京大学2003年中国古代史真题；中国人民大学2003年中国古代史真题；南京大学2014年中国古代史真题

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

高度为7的AVL树最少有()个结点。

我们知道，有些CPU指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，()可以不必具有此种特权。

常用的铣刀材料有哪两大类?各有什么特点?

抗菌药合理选择不包括

设随机变量X的概率密度为f(x)=，则P(1≤X≤4)=()。

在中国历史上曾经建立过统一全国的中央政权的少数民族有()。

我国实行“一国两制”不会改变人民民主专政国家的社会主义性质，这是因为：

在西亚最早创造文字的是()。

(2007年多选51)甲因海难下落不明，被法院宣告死亡。两年后，甲重新出现。法院依甲的申请撤销了对甲的死亡宣告。甲与原配偶的婚姻关系不能自行恢复的情形包括()。

WhydidthegirlinviteUncleSmithtodinner?

Usuallyhemanagedtofindplentyofworkto______himoverhardtimes,Ithinkitisagoodidea.