首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
admin
2009-05-15
71
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(D
n
(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为(28)。
选项
A、D
k
(i,j)=D
k
-1(i,j)+C(i,j)
B、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,j)+C(i,j)}
C、D
k
(i,j)=D
k
-1(i,k)+D
k
-1(k,j)
D、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}
答案
D
解析
从“D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中,我们得到一个提示,在求i,j之间最短路径的时候,会考虑它经过哪些节点能缩短原来的路径。在 D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}中,D
k
(i,j)表示i到j不经过k的路径长度,而 Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度,且min()函数用于找最小值,所以此式正确。
转载请注明原文地址:https://kaotiyun.com/show/hwxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
每个盘块512字节的目录文件存放在某一磁盘上,其中文件控制块占64B(文件名占用8B)。若采用“文件控制块分解法”将文件控制块分解成两部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。那么对于一个共
若信元在交换过程中出现拥塞,该信息被记录在信元头的(27)中。
ICMP报文封装在(24)协议数据单元中传送,在网络中起着差错和拥塞控制的作用。常用的ping程序中使用了回送请求/应答报文,以探测目标主机是否可以到达。
某请求分页存储管理系统中,容量为1MB的主存被划分为512块,其页表如表7-1所示。若给定一十进制逻辑地址为7058,其十进制物理地址是(11)。
设某单位路由器建立了以下的路由表,若收到分组的目的IP地址为128.96.37.151,则转发的端口是(63),若收到分组的目的IP是128.96.35.151,则转发的端口是(64),若该路由器是该单位与Internet连接的路由器,则该单位分得的IP地
Atypicalapplicationofthis(71)isADSL.Itisemergingasthetechnologyforhome-andsmall-officeInternetconnectivity.Itp
Networkmanagershavelongawaitedpracticalvoice-over-IP(VOIP)solutions.VOIPpromiseseasenetworkmanagementanddecreases(6
Networkmanagershavelongawaitedpracticalvoice-over-IP(VOIP)solutions.VOIPpromiseseasenetworkmanagementanddecreases(6
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
随机试题
世界是既成事物的集合体。()
在PowerPoint2010中,对于已创建的多媒体演示文档可以用()命令转移到其他未安装PowerPoint2010的机器上放映。
Doyouwanttoliveanother100yearsormore?Someexpertssaythatscientificadvanceswillonedayenablehumanstolasttens
通过平方根转化可改善以下何种类型资料的正态性和方差齐性
长期应用糖皮质激素停药时应注意
采用工程量清单方式招标,工程量清单必须作为招标文件的组成部分,其()由招标人负责。
为提高生产效率,南方公司拟对一套尚可使用5年的设备进行更新改造,新旧设备的替换将在当年内完成(即更新设备的建设期为0),不涉及增加流动资金投资,采用直线法计提设备折旧,适用的企业所得税税率为25%。相关资料如下;资料一:已知旧设备的原始价值为30万
注册会计师对计划审计工作进行的记录,应当包括下列()内容。
古希腊斯巴达教育的特征是()。
A、 B、 C、 D、 C
最新回复
(
0
)