全部科目 > 软件设计师 >
2011年下半年 上午试卷 综合知识
第 62 题
知识点 单源点最短路径   最短路径  
关键词 算法   最短路径  
章/节 计算机软件知识  
 
 
迪杰斯特拉（Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（62)策略的算法。
 
  A.  分治
 
  B.  动态规划
 
  C.  贪心
 
  D.  回溯
 
 




 
 
相关试题     图 

  第59题    2009年下半年  
邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有n个顶点、e条边的图，(59)。

  第17题    2012年下半年  
某软件项目的活动图如下所示。图中顶点表示项目里程碑，连接顶点的边表示包含的活动，则里程碑（16)在关键路径上，活动FG的松弛时间为（17)。

  第65题    2022年下半年  
采用Dijkstra算法求解下图A点到E点的最短路径，采用的算法设计策略是(64)，该最短路径的长度是(65)?。

相关试题     最短路径 

  第65题    2022年下半年  
采用Dijkstra算法求解下图A点到E点的最短路径，采用的算法设计策略是(64)，该最短路径的长度是(65)?。

  第64题    2022年下半年  
采用Dijkstra算法求解下图A点到E点的最短路径，采用的算法设计策略是(64)，该最短路径的长度是(65)?。

 
知识点讲解
· 单源点最短路径
· 最短路径
 
        单源点最短路径
        单源点最短路径是指给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。迪杰斯特拉提出了按路径长度递增的次序产生最短路径的算法。
 
        最短路径
               单源点最短路径
               单源点最短路径是指给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。迪杰斯特拉提出了按路径长度递增的次序产生最短路径的算法。
               每对顶点间的最短路径
               若每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，便可求得网中每一对顶点之间的最短路径。弗洛伊德提出了求最短路径的算法，该算法在形式上要简单一些。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有