利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节

admin2010-01-23 82

问题利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用D^k(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(Dⁿ(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://www.kaotiyun.com/show/LvxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节

软件设计师上午基础知识考试

软考中级

阅读以下说明，回答问题。1中的设计方案中，与Internet连接的路由器采用网络地址转换(NAT)。

系统流程图用于可行性分析中______　的描述。

阅读以下说明，填入(n)处。【说明】某网络结构如图2.1所示，如果Router3与网络4之间的线路突然中断，按照RIP路由协议的实现方法，路由表的更新时间间隔为30秒，中断30秒后Router2的路由信息表2.1和中断300秒后Router2

ISO为传输层定义了4种类型的服务原语，由传输服务用户产生的原语是(99)。

下面有关NTFS文件系统优点的描述中，(5)是不正确的。要把FAT32分区转换为NTFS分区，并且保留原分区中的所有文件，不可行的方法是(6)。

在UNIX操作系统中，若用户键入的命令参数的个数为1时，执行cat$1命令；若用户键入的命令参数的个数为2时，执行cat＞＞$2＜$1命令。请将下面所示的Shell程序的空缺部分补齐。case(51)in1)cat$1;;2)cat

目前PC机并行接口具有(4)等3种工作模式。

1分子氨基酸活化为氨基酰-tRNA，消耗高能键数为

容易发生白血病的疾病是

B型胃炎主要是由下列哪个原因引起?

患者，男，22岁，身发疮痍，甚者溃烂已1年余，久治无效。近一周眼睑突然水肿，延及全身，伴恶风发热，小便不利，舌质红，苔薄黄，脉搏浮数，治疗宜选

压片镜检可见到呈菊花状菌丝的是

A、欣快作用B、缩瞳作用C、镇痛作用D、镇咳作用E、胃肠活动变化吗啡激动中脑盖前核的阿片受体，引起（）

如图所示，下列关于平均固定成本AFC曲线、平均可变成本AVC曲线与平均成本AC曲线说法正确的是()。

四星级、五星级饭店若达不到规定标准，省、自治区、直辖市旅游局星级评定机构有权(　　)。

录囚制度开始于以下哪一个朝代?()

和的关系是()．

利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节

软件设计师上午基础知识考试

软考中级

阅读以下说明，回答问题。1中的设计方案中，与Internet连接的路由器采用网络地址转换(NAT)。

系统流程图用于可行性分析中______ 的描述。

阅读以下说明，填入(n)处。【说明】某网络结构如图2.1所示，如果Router3与网络4之间的线路突然中断，按照RIP路由协议的实现方法，路由表的更新时间间隔为30秒，中断30秒后Router2的路由信息表2.1和中断300秒后Router2

ISO为传输层定义了4种类型的服务原语，由传输服务用户产生的原语是(99)。

下面有关NTFS文件系统优点的描述中，(5)是不正确的。要把FAT32分区转换为NTFS分区，并且保留原分区中的所有文件，不可行的方法是(6)。

在UNIX操作系统中，若用户键入的命令参数的个数为1时，执行cat$1命令；若用户键入的命令参数的个数为2时，执行cat＞＞$2＜$1命令。请将下面所示的Shell程序的空缺部分补齐。case(51)in1)cat$1;;2)cat

目前PC机并行接口具有(4)等3种工作模式。

1分子氨基酸活化为氨基酰-tRNA，消耗高能键数为

容易发生白血病的疾病是

B型胃炎主要是由下列哪个原因引起?

患者，男，22岁，身发疮痍，甚者溃烂已1年余，久治无效。近一周眼睑突然水肿，延及全身，伴恶风发热，小便不利，舌质红，苔薄黄，脉搏浮数，治疗宜选

压片镜检可见到呈菊花状菌丝的是

A、欣快作用B、缩瞳作用C、镇痛作用D、镇咳作用E、胃肠活动变化吗啡激动中脑盖前核的阿片受体，引起（）

如图所示，下列关于平均固定成本AFC曲线、平均可变成本AVC曲线与平均成本AC曲线说法正确的是()。

四星级、五星级饭店若达不到规定标准，省、自治区、直辖市旅游局星级评定机构有权( )。

录囚制度开始于以下哪一个朝代?()

和的关系是()．

系统流程图用于可行性分析中______　的描述。

四星级、五星级饭店若达不到规定标准，省、自治区、直辖市旅游局星级评定机构有权(　　)。