首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2013-07-12
43
问题
已知加权有向图G如下,回答下列问题:
(1)画出该有向图G的邻接矩阵;
(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
选项
答案
(1)有向图G的邻接矩阵 [*] (2) [*]
解析
本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk—stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是:
(1)设置两个顶点的集合S和T=V—S,集合s中存放已找到最短路径的顶点,集合T存放当前还未找到最短路径的顶点。
(2)初始状态时,集合S中只包含源点v
0
,然后不断从集合T中选取到顶点v
0
路径长度最短的顶点“加入到集合S中,集合S每加入一个新的顶点“,都要修改顶点v
0
到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上“到该顶点的路径长度值中的较小值。
(3)此过程不断重复,直到集合T的顶点全部加入到S中为止。
转载请注明原文地址:https://kaotiyun.com/show/Srxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
保加利亚共产党于1990年4月改名为保社会党,它在政府中沦为少数派的时间是()。
下列会议中,讨论有关对日本法西斯问题的有()。①开罗会议②德黑兰会议③雅尔塔会议④波茨坦会议
简述第二国际建立的历史条件。
1911年,美国工程师()出版《科学管理原理》一书,奠定了科学管理的理论基础,被誉为“科学管理之父”。
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
试述18世纪末至19世纪末美国西进运动的进程及对美国近代化的影响。(华东师范大学1999年世界近现代史真题)
【《周礼》】中国人民大学2006年中国古代史真题;中山大学2013年历史学基础(A)真题;西北民族大学2017年中国史综合真题
【《台事专约》】华东师范大学2000年中国近现代史真题;中国人民大学2013年历史学综合真题
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
肺癌肺外表现中,以下哪项最常见
污泥厌氧消化采用中温和高温两种,实际工程中一般采用中温,原因是()。
一级建造师(矿业工程)注册执业的工程范围包括()。
投标人应当按照()的要求编制投标文件。
以下已经计提的资产减值准备,可以通过损益转回的有()。Ⅰ.以成本模式进行后续计量的投资性房地产Ⅱ.可供出售权益工具Ⅲ.存货Ⅳ.持有至到期投资
以引导探究为主的教学方法
(上海财大2013)将商业信用转化为银行信用可以通过()。
已知α1=(1,0,0)T,α2=(1,2,一1)T,α3=(一1,1,0)T,且Aα1=(2,1)T,Aα2=(一1,1)T,Aα3=(3,一4)T,则A=________。
设有幂级数(1)求该幂级数的收敛域;(2)证明此幂级数满足微分方程y"一y=一1;(3)求此幂级数的和函数:
在分布数据规划中存在多种数据分布形式,并可能产生数据同步问题,以下哪种数据不会存在同步问题?
最新回复
(
0
)