首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节
admin
2010-01-23
81
问题
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用D
k
(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(D
n
(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为(62)。
选项
A、D
k
(I,j)=D
k-1
(I,j)+C(I,j)
B、D
k
(I,j)=D
k-1
(I,k)+D
k-1
(k,j)
C、D
k
(I,j)=min{D
k-1
(I,j),D
k-1
(I,j)+C(I,j)}
D、D
k
(I,j)=min{D
k-1
(I,j),D
k-1
(I,K)+D
k-1
(k,j)}
答案
D
解析
设P
k
(I,j)表示从i到j并且不经过编号比k还大的节点的最短路径,那么P
k
(I,j)有以下两种可能:
①P
k
(I,j)经过编号为k的节点,此时P
k
(I,j)可以分为从i到k和从k到j的两段,易知P
k
(I,j)的长度为D
k-1
(I,k)+D
k-1
(k,j);
②P
k
(I,j)不经过编号为k的节点,此时P
k
(I,j)的长度为D
k-1
(I,j)。
因此,求解该问题的递推关系式为:D
k
(I,j)=min{D
k-1
(I,j),D
k-1
(I,k)+D
k-1
(k,j)}。
转载请注明原文地址:https://kaotiyun.com/show/LvxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
HFC网络即光纤同轴混合网(Hybrid Fiber Coax),它是近年来我国有线电视接入网技术体制的主要形式,HFC所使用的传输技术是(71),综合接入多种业务。HFC的用户端,从PC机接收的以太帧被封装在时隙中,经过(72)调制后,通过HPC网络的上
可维护性的特性中相互促进的是______ 。
请列举IEEE802.11b的两种工作模式。列举蓝牙产品采用的主要技术内容。
在自治系统内部的各个路由器之间,运行的是内部网关协议IGP。早期的IGP叫做(51),它执行(52)。当网络规模扩大时,该算法使得传送的路由信息太多,增加了网络负载,后来又出现了执行最短路径优先算法的IGP。按照这种协议,每个路由器向网络中的其他路由器发布
RSA是一种基于(43)原理的公钥加密算法。网络上广泛使用的PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(44)。POP还可以对电子邮件进行认证,认证机制是用MD5算法产生(45)位的报文摘要,发送方用自己的RSA私钥对
IEEE802.11定义了无线局域网的两种工作模式,其中(45)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,用无线网卡连接的设备之间可以直接进行通信。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接序列扩频(DSSS)
I/O系统主要有三种方式来与主机交换数据,它们是(6)、(7)和(8)。其中(6)主要用软件方法来实现,CPU的效率低;(7)要有硬件和软件两部分来实现,它利用专门的电路向CPU中的控制器发出I/O服务请求,控制器则(9)转入执行相应的服务程序;(8)主要
软件能力成熟度模型CMM(CapabilityMaturityModel)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇。在(7)
某项目主要由A~I任务构成,其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位:天),该项目的关键路径是()。在不延误项目总工期的情况下,任务A最多可以推迟开始的时间是()天。
随机试题
手术前1天的准备内容不包括该患者术后护理内容应除外
二类精神药品处方的颜色是
基金销售费用包括()。Ⅰ.申购(认购)费Ⅱ.销售服务费Ⅲ.基金管理费Ⅳ.赎回费
根据消费税法律制度的规定,下列各项中,属于消费税征税范围的消费品有()。
某大型企业成立于五十年代初,经过多年的努力,目前已在市场中占据了一席之地,在业内已具有较高的知名度。目前该公司有员工一千人左右,总公司下设有若干子公司,分别从事不同的业务。卓越绩效评价工作是公司重点投入的一项工作。公司的高层领导非常重视,为评价其经营管理模
两个人约定在某一指定地点会面:时间定在中午12点与下午1点之间。根据约定,第一个到达的人等第二个人15分钟,然后就离开,如果这两个人都随机地在中午12点至下午1点之间选择各自的到达时刻,问他们实际相遇的概率是多少?
Almosteverydayweseesomethinginthepapersaboutthelatestexcitingdevelopmentsinthespacerace.Photographsareregula
Dopeoplegethappierormorefoul-temperedastheyage?Stereotypesofirritableneighbors【C1】______,scientistshavebeentryi
设有如下程序:PrivateSubsV(ByValmAsInteger,nAsInteger)m=m*2:n=n一5:Printm:nEndSubPrivateSubForm_C
WhenItellpeoplethatI’maprofessorofcommunication,theyoftenareconfused【C1】______whattheterm"communication"means.
最新回复
(
0
)