首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
已知加权有向图G如下,回答下列问题: (1)画出该有向图G的邻接矩阵; (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
admin
2012-06-26
63
问题
已知加权有向图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中选取到顶点b>路径长度最短的顶点u加入到集合S中,集合S每加入一个新的顶点u,都要修改顶点b>到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。
(3)此过程不断重复,直到集合T的顶点全部加入到S中为止。
转载请注明原文地址:https://jikaoti.com/ti/DhajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
确定我国经济体制改革目标的核心问题是正确认识和处理()。
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
论述近代西欧海上霸权的更迭
第一国际成立于下面的哪个城市?()
以德国宗教改革为例分析宗教改革产生的原因和作用。
以下选项不属于希腊城邦的形成方式和途径的是()。
洋务派创办军事工业的方式是()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
对于一个长度为n的任意表进行排序,至少需要进行的比较次数是()。
随机试题
不符合特发性血小板减少性紫癜的实验室检查是
有关常伴有并发症的右心衰竭,下述各项不会出现的是
与地下快速公路相比,半地下公路的特点是()。
步进电动机的位移总量主要取决于()。
根据合伙企业法律制度的规定,下列各项中,属于合伙企业应当解散的情形有()。
造成性行为问题的原因总括起来,不外乎()、心理因素和生理因素三大类。
结合材料回答问题:材料13月15日上午,国务院总理李克强在人民大会堂会见采访十二届全国人大三次会议的中外记者,并回答记者提出的问题。在回答关于雾霾等环境污染问题时,总理指出:治理要抓关键,今年的要害就是要严格执行新出台的《环境保护法》。
n个顶点的强连通图的边数至少有______。
要在报表的页脚输出当前系统日期和时间,则应将相应文本框的控件来源属性设置为
负责数据库中查询操作的数据库语言是( )。
最新回复
(
0
)