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

admin2010-01-23 99

问题利用动态规划方法求解每对节点之间的最短路径问题(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还大的节

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

软考中级

阅读以下说明；回答下面问题。【说明】Windows组网是将主机和服务器连接起来的重要手段。下图3.2给出了在Windows操作系统中的典型LAN配置。

在流通领域中用于标识商品的(1)的通用条码被称作商品条码。条码中的(2)供人们直接识读，或通过键盘向计算机输入数据。

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

阅读以下说明，回答下面问题。【说明】在atm(asynchronoustransfermode)传输模式中，信息被组织成信元，因包含来自某用户信息的各个信元不需要周期性出现，这种传输模式是异步的。由于atm技术简化了交换过程，去处了不必要

阅读以下说明，回答下面问题。【说明】某公司下设三个部门，为了便于管理，每个部门组成一个VLAN，公司网络结构如图2.3所示。

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

目前，通过移动电话接入互联网所采用的主要技术是什么?目前，国内采用的第三代移动通信技术标准有哪些?

四台Linux主机通过图1所示的方式互联起来，则实现PCI与PC4之间互访的步骤为：1．运行(46命令关闭计算机，在PC2与PC3上添加第二块网卡(ethl)，重新启动；2．在PC2与PC3上为第二块网卡分配IP地址，并激活该网络接口，对

某一定点数字长为n位，且最高位是符号位，小数点位于最低有效数值位之后，则该机器数所能表示的最小值是(2)。

某机器字长为n，最高位是符号位，其定点整数的最大值为(2)。

Lifewithoutbooksisincomplete.Booksinfluencethedepthandbreadthoflife.Theymeetthenatural【B1】______forfreedom,for

I’vemadean______foryoutoseethedoctorat5’oclock.

关于心电图临床诊断价值的表述，不正确的是

均价的制定参照比较楼盘时的比较因素有()。

下列选项中，属于高效减水剂的是()。

根据规定，企业职工伤亡事故统计实行以()为主的制度。

1949年7月，中央决定在华北社会部和华北公安部的基础上组建中央军委公安部。(　　)

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

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

软考中级

阅读以下说明；回答下面问题。【说明】Windows组网是将主机和服务器连接起来的重要手段。下图3.2给出了在Windows操作系统中的典型LAN配置。

在流通领域中用于标识商品的(1)的通用条码被称作商品条码。条码中的(2)供人们直接识读，或通过键盘向计算机输入数据。

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

阅读以下说明，回答下面问题。【说明】在atm(asynchronoustransfermode)传输模式中，信息被组织成信元，因包含来自某用户信息的各个信元不需要周期性出现，这种传输模式是异步的。由于atm技术简化了交换过程，去处了不必要

阅读以下说明，回答下面问题。【说明】某公司下设三个部门，为了便于管理，每个部门组成一个VLAN，公司网络结构如图2.3所示。

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

目前，通过移动电话接入互联网所采用的主要技术是什么?目前，国内采用的第三代移动通信技术标准有哪些?

四台Linux主机通过图1所示的方式互联起来，则实现PCI与PC4之间互访的步骤为：1．运行(46命令关闭计算机，在PC2与PC3上添加第二块网卡(ethl)，重新启动；2．在PC2与PC3上为第二块网卡分配IP地址，并激活该网络接口，对

某一定点数字长为n位，且最高位是符号位，小数点位于最低有效数值位之后，则该机器数所能表示的最小值是(2)。

某机器字长为n，最高位是符号位，其定点整数的最大值为(2)。

Lifewithoutbooksisincomplete.Booksinfluencethedepthandbreadthoflife.Theymeetthenatural【B1】______forfreedom,for

I’vemadean______foryoutoseethedoctorat5’oclock.

关于心电图临床诊断价值的表述，不正确的是

均价的制定参照比较楼盘时的比较因素有()。

下列选项中，属于高效减水剂的是()。

根据规定，企业职工伤亡事故统计实行以()为主的制度。

1949年7月，中央决定在华北社会部和华北公安部的基础上组建中央军委公安部。( )

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

1949年7月，中央决定在华北社会部和华北公安部的基础上组建中央军委公安部。(　　)