最短路径问题的概念和形式
旧城暖人心
精选回答
一、最短路径问题的概念和形式
1、最短路径问题
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
2、最短路径问题的形式
(1)确定起点的最短路径问题:即已知起始结点,求最短路径的问题。
(2)确定终点的最短路径问题:与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于将问题变为反向来确定起点的问题。
(3)确定起点终点的最短路径问题:即已知起点和终点,求两结点之间的最短路径。
二、最短路径问题的相关例题
一只蚂蚁从圆柱体的下底面$A$点(左下角)沿着侧面爬到上底面$B$点(右上角),已知圆柱的底面半径为2cm,高为8cm(π取3),则蚂蚁所走过的最短路径是___
A.8 B.9 C.10 D.12
答案:C
解析:把圆柱侧面展开,点$A$、$B$的最短距离为线段$AB$的长。在Rt$△ABC$中,$∠ACB=90°$,$BC$=8cm,$AC$为底面半圆弧长,$AC$=2π=6cm,所以$AB =\sqrt{AC^2+BC^2}$=10cm。故选C。
顺其自然 2024-05-22 11:13:17
相关推荐
国考研究生能不能以本科专业报名
在国家公务员考试中,招录职位表中所要求的学历为报考人员所获得的最高学历。社会在职人员应以获得的最高学历进行报考,应届高校毕业生以即将获得的最高学历进行报考。如,招录职位表中要求限本科学历的,硕士研究生和博士研究...
展开详情考研后第一学历是什么
考研后第一学历是什么如果读完本科后直接进行考研,进修研究生,那第一学历为硕士;如果本科毕业参加工作后,才进修研究生,那第一学历就是本科。第一学历是不间断的普通全日制教育的最高学历。考验后的第一学历是什么1、如果...
展开详情兰州理工大学学费
兰州理工大学学费兰州理工大学学费为建筑学、城市规划专业5500元/学年;工科类专业4700元/学年;艺术类专业6800元/学年;理科类专业4300元/学年;外语类专业4400元/学年;其他类专业学费为4000元...
展开详情适合专科生考研的学校
适合专科生考研的学校适合专科生考研的学校有中国人民大学、北京工业大学、北京交通大学、天津大学、南开大学、华中科技大学、武汉大学、湖南大学、吉首大学、湘潭大学、吉林大学、延边大学、长春理工大学、河北大学、河南大学...
展开详情高考农村专项计划报名条件
高考农村专项计划报名条件高考农村专项计划报名条件为需要为国家专项计划定向招收贫困地区学生;需要为地方专项计划定向招收各省实施区域的农村学生;需要为边远、贫困、民族等地区县以下高中勤奋好学、成绩优良的农村学生。高...
展开详情