首页 > 常见问题 > 正文

最短路径问题

原创 2019-06-15 09:09:28 0 258
第七期线上培训班
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 最短路径问题是组合优化领域的经典问题之一,它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域。Dijkstra算法是经典的最短路径算法。

算法具体的形式包括:(推荐学习:PHP视频教程

确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。

确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。

全局最短路径问题 - 求图中所有的最短路径。

Dijkstra算法

Dijkstra算法是经典的最短路径算法,其基本思想是:设置一个集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v,对vi∈V-S,假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk,就将vk加入集合S中,并将路径v, …, vk , vi与原来的假设相比较,取路径长度较小者为最短路径,重复上述过程,直到集合V中全部顶点加入到集合S中。使用该算法找到的是全局最优的最短路径,在网络节点数量大、网络边数较多时,存在内存占用大、时间复杂度高等不足,并且Dijkstra算法不能很好地解决含必经点约束的最短路径问题。

蚁群算法

蚁群算法是由Dorigo、Maniezzo和Colorni等于1991 年首先提出来的,它来源于蚂蚁寻食的行为。通过研究发现,蚂蚁个体之间是通过一种叫做信息素的外激素进行信息传递的。蚂蚁在行走过程中能感知周围信息素的强度, 并朝着信息素浓度高的方向移动,当某只蚂蚁发现食物时,它在回巢的过程当中,会在返回的路上释放信息素作为标记,同伴发现后会沿着此路寻找到食物。当同伴中多只蚂蚁都发现了食物但路径长短不同时,因为蚂蚁在短的路径上往返所需要的时间相对较小,所以单位时间内走过的蚂蚁越来越多,在这条路径上的信息素浓度就会越强,因此,该路径上的蚂蚁就会越来越多,逐渐选出一条最优的道路。

分类

可分成两个子问题,即单源最短路径问题和所有顶点对之间的最短路径问题。前者是找出从某一顶点出发到图中所有其他顶点的最短路径,主要算法有迪克斯彻算法等;后者是求图中每一对顶点之间的最短路径,主要算法有弗洛伊德算法等。

更多PHP相关技术文章,请访问PHP图文教程栏目进行学习!

以上就是最短路径问题的详细内容,更多请关注php中文网其它相关文章!

php中文网最新课程二维码
  • 相关标签:最短路径
  • 本文原创发布php中文网 ,转载请注明出处,感谢您的尊重!
  • 相关文章


  • 在SQL Server实现最短路径的搜索
  • 单流最短路径(dijkstra算法)php实现
  • 单源最短路径(dijkstra算法)php实现
  • php实现Dijkstra(迪科斯彻)最短路径算法的示例
  • 最短路径问题
  • 网友评论

    文明上网理性发言,请遵守 新闻评论服务协议

    我要评论
    独孤九贱(5)_ThinkPHP5视频教程

    独孤九贱(5)_ThinkPHP5视频教程

    ThinkPHP是国内最流行的中文PHP开发框架,也是您Web项目的最佳选择。《php.cn独孤九贱(5)-ThinkPHP5视频教程》课程以ThinkPHP5最新版本为例,从最基本的框架常识开始,将...

    独孤九贱(4)_PHP视频教程

    独孤九贱(4)_PHP视频教程

    江湖传言:PHP是世界上最好的编程语言。真的是这样吗?这个梗究竟是从哪来的?学会本课程,你就会明白了。 PHP中文网出品的PHP入门系统教学视频,完全从初学者的角度出发,绝不玩虚的,一切以实用、有用...

    独孤九贱(1)_HTML5视频教程

    独孤九贱(1)_HTML5视频教程

    《php.cn原创html5视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了HTML知识。 ...

    ThinkPHP5实战之[教学管理系统]

    ThinkPHP5实战之[教学管理系统]

    本套教程,以一个真实的学校教学管理系统为案例,手把手教会您如何在一张白纸上,从零开始,一步一步的用ThinkPHP5框架快速开发出一个商业项目。

    PHP入门视频教程之一周学会PHP

    PHP入门视频教程之一周学会PHP

    所有计算机语言的学习都要从基础开始,《PHP入门视频教程之一周学会PHP》不仅是PHP的基础部分更主要的是PHP语言的核心技术,是学习PHP必须掌握的内容,任何PHP项目的实现都离不开这部分的内容,通...

    作者信息

    (*-*)浩

    认证0级讲师

    最近文章
    python list和tuple的区别 449
    anaconda和python区别 724
    python数组和列表区别 983

    相关视频教程

  • php全栈开发之小博客大智慧 php全栈开发之小博客大智慧
  • PHP每日小知识(第二季) PHP每日小知识(第二季)
  • PHP语法基础与数据库详解教程 PHP语法基础与数据库详解教程
  • PHP数据库编程零基础入门到精通 PHP数据库编程零基础入门到精通
  • 相关视频章节

    第七期线上培训班