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

admin2012-06-26 107

问题已知加权有向图G如下，回答下列问题：

(1)画出该有向图G的邻接矩阵；
(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

选项

答案(1)有向图G的邻接矩阵 [*] (2) [*]

解析本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk-stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是：
(1)设置两个顶点的集合S和T=V—S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。
(2)初始状态时，集合S中只包含源点v₀，然后不断从集合T中选取到顶点b>路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点b>到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。
(3)此过程不断重复，直到集合T的顶点全部加入到S中为止。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

战国时代百家争鸣的局面，是我国学术文化发展的重要阶段，在激烈的争鸣中，有着融合的趋向，下列选项中，不能体现这一特点的是()

试析淝水之战前后南北政权的特点和变化。

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

在网络中计算机接收的信号是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

外胚层的分化主要包括、和的形成。

电生理学检查有助于臂丛神经损伤的定位检查，下列叙述错误的是

膈肌上的腔静脉孔、食管裂孔、主动脉裂孔分别对应于

钱乙的学术思想是

根据《执业药师资格制度暂行规定》，执业药师的执业范围是()。

福利管理的主要原则是()。

【2014．河北石家庄】“自信、勤奋、乐观”描写的是人的()心理特征。

将一个硬币掷两次，恰好有一次正面朝上且有一次反面朝上的概率是多少?()。

神经元由细胞体、轴突和——三部分组成。

下列对子网系统的防火墙的描述，错误的是______。

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

计算机408

学硕统考专业

战国时代百家争鸣的局面，是我国学术文化发展的重要阶段，在激烈的争鸣中，有着融合的趋向，下列选项中，不能体现这一特点的是()

试析淝水之战前后南北政权的特点和变化。

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

1948年，南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法，其核心是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

在网络中计算机接收的信号是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

外胚层的分化主要包括________、________和________的形成。

电生理学检查有助于臂丛神经损伤的定位检查，下列叙述错误的是

膈肌上的腔静脉孔、食管裂孔、主动脉裂孔分别对应于

钱乙的学术思想是

根据《执业药师资格制度暂行规定》，执业药师的执业范围是()。

福利管理的主要原则是()。

【2014．河北石家庄】“自信、勤奋、乐观”描写的是人的()心理特征。

将一个硬币掷两次，恰好有一次正面朝上且有一次反面朝上的概率是多少?()。

神经元由细胞体、轴突和——三部分组成。

下列对子网系统的防火墙的描述，错误的是______。

外胚层的分化主要包括、和的形成。