首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对节点之间的最短路径问题(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
52
问题
利用动态规划方法求解每对节点之间的最短路径问题(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
用户甲与用户乙通过卫星链路通信时,传播延迟为135ms,数据速率是64Kb/s,帧长2000bit,若采用停等流控协议,则最大链路利用率为(115);若采用后退N帧ARQ协议通信,发送窗口为8,则最大链路利用率可以达到(116)。
可维护性的特性中相互促进的是______ 。
说明现有虚拟局域网络的四种划分方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪三种模式划入VLAN中,并简述它们的含义。
阅读以下说明,回答下面问题。【说明】A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过具有数据显示功能的移动电话或PDA(Personal-DigitalAssist
虚拟存储管理系统的基础是程序的(30)理论。这个理论的基本含义是指程序执行往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁访问的页面集合。在进程运行时,如果它的工作集页面都在(31)内,则能够使该进程有
ISO为传输层定义了4种类型的服务原语,由传输服务用户产生的原语是(99)。
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(28)媒体访问控制方法,IEEE802.5标准采用(29)媒体访问控制方法。其中(30)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mb
虚拟存储管理系统的基础是程序的(7)理论,这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时,如果它的工作集页面都在(8)内,能够使该进程有效
IEEE802.11定义了无线局域网的两种工作模式,其中(45)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,用无线网卡连接的设备之间可以直接进行通信。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接序列扩频(DSSS)
对文法G进行改写,然后对每个非终结符写出不带回溯的递归于程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
随机试题
市里准备选拔并通过媒体表彰一批优秀大学生村干部,如果你是市委组织部工作人员,领导安排你来组织此次评选工作,你会如何进行大学生村干部优秀事迹的搜集和筛选工作?
常用的卫生保健资源指标包括_______、_______和_______。
下列属于家庭病床收治范围的是
砂浆锚杆的灌浆强度应不低于()。
(2017年第40题)下列楼板平面布置图中,建筑形体平面规则的是()。
关于室内燃气管布置方案,下列叙述正确的是()。
汇率决定理论是研究两种货币间兑换关系的内在规律性的理论。理论汇率等于两国一般物价水平之比的观点,属于( )。
1931年11月,在江西瑞金召开的第一次中华苏维埃工农兵代表大会上,成立了中华苏维埃临时中央政府,组建了我国最早的人民政权公安保卫机关。这一机关是:
过去,人们很少在电脑上收到垃圾邮件。现在,只要拥有自己的电子邮件地址,人们一打开电脑,每天可以收到几封甚至数十封包括各种广告和无聊内容的垃圾邮件。因此,应该制订限制各种垃圾邮件的规则并研究反垃圾的有效方法。以下哪项如果为真.最能支持上述论证?
Burglars______andstolesomemoneywhilethefamilywasaway.
最新回复
(
0
)