更多"网络模型中使用的最短路径算法可用来:"的相关试题:
[单项选择]迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径,本质上说,该算法是一种基干()策略的算法。
A. 分治
B. 动态规划
C. 贪心
D. 回溯
[单项选择]
求最短路径的FLOYD算法的时间复杂度为()
A. O(n)
B. O(n+e)
C. O(n
2)
D. O(n
3)
[单项选择]迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题,该算法运用了()算法策略。
A. 贪心
B. 分而治之
C. 动态规划
D. 试探+回溯
[单项选择]以下几种算法中可以求解起讫点不同的单一路径规划(最短路径问题)的是______。
A. 扫描法
B. 表上作业法
C. 单纯形法
D. Dijkstra算法
[单项选择]开放最短路径优先协议(OSPF)采用 (22) 算法计算最佳路由。
A. Dynamic-Search
B. Bellman-Ford
C. Dijkstra
D. Spanning-Tree
[单项选择]下列选项中,关于最短路径优先协议的描述不正确的是( )。
A. 主要的特征是使用分布式链路状态协议
B. OSPF协议要求路由器发送的信息是有关本路由器与哪些路由器相邻,以及链路状态的度量
C. 是一种分布式、基于距离向量的路由选择协议,其特点是协议简单
D. OSPF协议要求当链路状态发生变化时用洪泛法向所有路由器发送此信息
[简答题]带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v:
③重复步骤②,直到u是目标顶点时为止。
请问上述方法能否求得最短路径若该方法可行,请证明之;否则,请举例说明。
[单项选择]利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为()。
A. Dk(I,j)=Dk-1(I,j)+C(I,j)
B. Dk(I,j)=Dk-1(I,k)+Dk-1(k,j)
C. Dk(I,j)=minDk-1(I,j),Dk-1(I,j)+C(I,j)
D. Dk(I,j)=minDk-1(I,j),Dk-1(I,K)+Dk-1(k,j)
[单项选择]开放最短路径优先协议(OSPF)采用______算法计算最佳路由。
A. Dynamic-Search
B. Bellman-Ford
C. Dijkstra
D. Spanning-Tree
[判断题]铁路货运运费是按计费里程计费的,而公路货运运费是按照发站至到站最短路径计算的。
[单项选择]A和B为正方体两个相对的顶点,一个点从A出发沿正方体表面以最短路径移动到B,则其可选择的路线有几条( )
A. 2
B. 3
C. 6
D. 12
[单项选择]利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为()。
A. Dk(i,j)=Dk-1(i,j)+C(i,j)
B. Dk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j)
C. Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)
D. Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)
[单项选择]OSI模型中完成路径选择功能的层次是( )。
A. 物理层
B. 数据链路层
C. 网络层
D. 传输层
[填空题]所谓最佳路径是指经过的结点最少或者传输______最短。