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

admin2012-06-26 108

问题已知加权有向图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://www.kaotiyun.com/show/3fxi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

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

巴黎和会讨论的中心问题是()。

德国法西斯能够通过合法方式夺取政权，主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党

下列不是在北伐战争中发生的是()

东汉时期，一再削弱地方的军权，强化中央控制下的军队，在下列中央控制的军队中，主要负责保卫京师的是()

论述近代西欧海上霸权的更迭

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：该网络发送一帧的发送延时和传输延时分别是多少?

简述律师民事法律责任的特征。

ICSH建议血细胞计数用抗凝剂是

手术过程中，用于心跳骤停的急救药物是

对病毒生物学性状的描述，不正确的是

根据相关资料缮制出口单据。信用证资料如下：27：SEQUENCEOFTOTAL：1／140A：FORMOFDOCUMENTARYCREDIT：IRREVOCABLE20：DOCUMENTARYCREDITNUMBER：HBZK

(　　)的资金来源是中国人民银行的再贷款，资金用于农业生产和建设。

信用风险的主要形式包括()。

我国《个人所得税法》规定：工资、薪金所得，以每月收入额减除费用()元后的余额，为应纳税所得额。

某班有十名学生参加了学校举办的化学竞赛，已知前八名的平均成绩是80分，第九名比第十名多2分。所有学生的平均成绩是77分。第九名学生的化学成绩是()分。

符号(复旦大学2018年研；北交2016年研；温州大学2015年研；中国传媒大学2014年研；华东师大2014年研；南京大学2013年研；华农2010年研)

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

计算机408

学硕统考专业

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

巴黎和会讨论的中心问题是()。

德国法西斯能够通过合法方式夺取政权，主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党

下列不是在北伐战争中发生的是()

东汉时期，一再削弱地方的军权，强化中央控制下的军队，在下列中央控制的军队中，主要负责保卫京师的是()

论述近代西欧海上霸权的更迭

记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知一个线性表(38，25，74，63，52，48)，表长为16，假定采用散列函数h(key)=key％7，计算散列地址，并存储在散列表中，若采用线性探测方法解决冲突，在该散列表上，进行等概率成功查找的平均查找长度为()。

如下图所示为一个带宽为50kbps的卫星信道，它的往返传播延时为500ms。现在有一个网络架设在该信道上，网络使用1000bit长度的帧和停止一等待协议，请回答如下问题：该网络发送一帧的发送延时和传输延时分别是多少?

简述律师民事法律责任的特征。

ICSH建议血细胞计数用抗凝剂是

手术过程中，用于心跳骤停的急救药物是

对病毒生物学性状的描述，不正确的是

根据相关资料缮制出口单据。信用证资料如下：27：SEQUENCEOFTOTAL：1／140A：FORMOFDOCUMENTARYCREDIT：IRREVOCABLE20：DOCUMENTARYCREDITNUMBER：HBZK

( )的资金来源是中国人民银行的再贷款，资金用于农业生产和建设。

信用风险的主要形式包括()。

我国《个人所得税法》规定：工资、薪金所得，以每月收入额减除费用()元后的余额，为应纳税所得额。

某班有十名学生参加了学校举办的化学竞赛，已知前八名的平均成绩是80分，第九名比第十名多2分。所有学生的平均成绩是77分。第九名学生的化学成绩是()分。

符号(复旦大学2018年研；北交2016年研；温州大学2015年研；中国传媒大学2014年研；华东师大2014年研；南京大学2013年研；华农2010年研)

(　　)的资金来源是中国人民银行的再贷款，资金用于农业生产和建设。