• 尚大品牌
    • 尚大网校|在线考试|证书查询|成绩查询
    登录   |   注册
     
     
        准考证打印   论文投票   报考指南   论文辅导   软考培训   郑重申明  
    您现在的位置：  首页 > 软考学苑 > 系统集成项目管理工程师 > 中项上午综合知识 > 中项章节知识点 >> 正文
    正文
    最短路问题
    来源：尚大教育-软考学院 作者：尚大教育 时间;2018-04-27 10:35:19 点击数： 尚大软考交流群：376154208
    （最短路问题）设 G=（V,E）是连通图，图中各边（vi,vj）有权 wi,j=w（vi,vj）。设 vs 和 vt 是 G 中任意两点， P 是一条从 vs 到 vt 的路径，求一条路 P*，使它是从 vs 到 vt 的所有路径中总权和最小的路，就称这条路径为从 vs 到 vt 的最短路。最短路问题的求解方法之一为标注法。
    从起点开始，计算它到下一个节点（二级节点）的各个路径长度，选择其中的最小值，标注在该二级节
    <尚大教育，教育至上，人才为大：sdedu.cc>
    （最短路问题）设 G=（V,E）是连通图，图中各边（vi,vj）有权 wi,j=w（vi,vj）。设 vs 和 vt 是 G 中任意两点， P 是一条从 vs 到 vt 的路径，求一条路 P*，使它是从 vs 到 vt 的所有路径中总权和最小的路，就称这条路径为从 vs 到 vt 的最短路。最短路问题的求解方法之一为标注法。
     
    1. 从起点开始，计算它到下一个节点（二级节点）的各个路径长度，选择其中的最小值，标注在该二级节点旁；
     
    1. 从二级节点开始，计算它到下一个节点（三级节点）的各个路径长度，选择其中的最小值，标注在该三级节点旁；
     
    1. 重复上述步骤，直至终点节点。
     
    求从 v1 出发到 v8 总费用最小的路线。
     

    按照介绍的标注法，可得例中的最短路径为 V1，V2，V5，V8，最低费用（最短路径）为 12。
     
    <尚大教育，教育至上，人才为大：sdedu.cc>
     
       各省软考办 
     
    来顶一下
    返回首页
    返回首页
    上一篇：31.4 图论
    下一篇：设备更新问题
     相关文章
     
     
    跟贴共条
    查看完整评论
    笔 名 ：   验证码：
    网友评论仅供其表达个人看法，并不表明尚大教育同意其观点或证实其描述
    距离2023年05月27-28日软考考试还有 天
    尚大软考交流群：376154208
    软考各地考务机构
    更多>>
    全国 北京 天津 河北 山西
    内蒙古 辽宁 吉林 黑龙江 上海
    江苏 浙江 安徽 福建 江西
    山东 河南 湖北 湖南 广东
    广西 海南 重庆 四川 贵州
    云南 西藏 陕西 甘肃 青海
    宁夏 新疆 香港 澳门 宁波
    大连 兵团 报名入口 联系方式
    历年真题汇总
    更多>>




    各省市软考报名简章
    软考动态
    更多>>
    PMI, PMP, Project Management Professional, PgMP, PfMP, PMI-ACP, PMI-PBA, PMBOK and the PMI Registered Education Provider logo are registered marks of the Project Management Institute, Inc.   京ICP备12019404号  Copyright© 2008-2021 北京翰林尚大教育科技有限公司