欢迎光临本站!

最短路径搜索算法的优化途径

来源:技术探讨    更新时间:2019-12-20 14:57:42    编辑:老王    浏览:728

  原始Dijkstrfl算法将网络结点分为未标记结点、l临时标记结点和永久标记结点3种类型。网络中所有结点首先初始化为朱标记结点,在搜索过程中和最短路径结点相连通的结点为临时标记结点,每一次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点,直至找到目标结点或者所有结点都成为永久标记结点才结束算法。

  在原始Dijkstra算法中。临时标记结点无序地存储在无序表中,这无疑成为Dijkstra算法的瓶颈,因为每次在临时标记点中搜索路径最短的结点时,都要遍历所有的临时标记结点。解决的办法就是将临时标记结点按照最短路径排序,每个搜索过程不必全部遍历或者只较少地遍历临时标记点,这也是目前各种基于原始Dijkstra算法的各种优化算法的重要出发点之一;另外一个优化途径是尽量减少最短路径分析过程中搜索的临时结点数量,从而尽快到达目标结点。

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜