首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对节点之间的最短路径问题(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
66
问题
利用动态规划方法求解每对节点之间的最短路径问题(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
以下选项中不采用组播协议的应用是(125)。在IPV4地址中,(126)类地址作为组播地址。
应用程序可以通过执行对象的操作来改变对象的属性值,但它必须通过 ______ 的传递。
计算机网络和分布系统中互相通信的(303)间交换信息时必须遵守的规则的集合称之为网络协议。其中,(304)是数据和控制信息的结构或格式;(305)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(306)。
由我国信息产业部批准发布,在信息产业部门范围内统一使用的标准,称为(24)。
交换机的所有端口在缺省配置的情况下(52)。如果属于同一VLAN的数据帧是连接在不同交换机上的,必须通过(53)传输。
代号(5)按中央所属企业或地方企业分别由国务院有关行政主管部门或省、自治区、直辖市政府标准化行政主管部门会同同级有关行政主管部门加以规定,没有强制性和推荐之分。
用户A与用户B通过卫星链路通信时,传播延迟为540ms,假设数据速率是64Kbit/s,帧长4000bit,若采用停等控制协议通信,则最大链路利用率为(22);若采用后退N帧ARQ协议通信,发送窗口为8,则最大链路利用率可以达到(23)。
对一路信号进行频移键控(FSK)调制时,若载波频率为fc,调制后的信号频率分别为f1和f2(f1<f2),则三者的关系是(17)。当对多路信号进行调制时,调制后各信号的频谱(18)。信号到达接收端后通过(19)分离各路信号。WDM与FDM工作方式很相似,
发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障的情况下系统正常工作。带有热备份的系统称为(61)系统。它是(62),因此只要有一个子系统能正常工作,整个系统仍能正常工作。当子系统只能处于正常工作和不工作两种状态时,可以采用如图
DES加密算法中,函数f的输出是(51)位。DES算法是分组密码,数据分组长度是(52)位。用软件方法实现DES一般至少比RSA快100倍。DES通过(53)方法产生密文。
随机试题
为了投靠帝国主义,袁世凯的卖国行为表现在
认识是主体对客体的能动反映,这是( )
一侧乳房胀痛,喂奶时应
医疗保险制度的覆盖范围是
A.1年B.5年C.3年D.4年E.2年药品验收记录保存至超过药品有效期是()
下图ab段表示的实际地形为()。
取得《报检员证》的人员,可以兼任两个公司的报检工作。( )
甲公司是ABC会计师事务所的常年审计客户,主要从事化工产品的生产和销售,A注册会计师负责审计甲公司2013年财务报表。注册会计师于2014年3月1日完成审计工作。资料一:(1)甲公司2012年生产a产品1000件,全部采用直销形式,2013年起甲公司决
改进岗位设计可以从很多方面人手,但不包括()。
Whatistheearliestrecordofalcoholabout?
最新回复
(
0
)