空间搜索Dijkstra算法

作者: 阳春是你 | 来源:发表于2016-05-13 18:40 被阅读117次

一、简介

一、Dijkstra算法简介
参考资料
http://www.cqvip.com/read/read.aspx?id=10224130
http://baike.baidu.com/link?url=3a1DNfU-tC_qbaT0euM67hqy-7dewsuc2_WwGppfwIsyCjZQ-bQHN_XIwnb5bT_vcfuDYws2Ox4DtozUsRG0jq

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的。用于求一个顶点到其余各顶点的最短路径,解决的是有向图中最短路径问题。该算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

Dijkstra算法基本思想是从起点(1)开始,遍历相邻的点(二层的2,3),计算相邻的点到此点的距离, 然后再计算与第二层相邻的点(4,5到2的距离,5,6到3的距离),直至遍历到结束点。


Paste_Image.png

如,若要求点1到点5的距离。可以
设保存各点到点1的距离的集合 为U({2(10)}表示2到1的距离为10,1(0)表示1到自己的距离为0),设待遍历的点的集合为S,则每次循环可以得到的S和U如下。

这个例子中,我们通过3次循环,得到了1到5的最短长度8,即可以说明1,3,5这条路径为最短路径。

<b>邻接表的构建</b>
在程序实现中,我们使用邻接表来表示这个有向带全图。在上例中,上例的图,其顶点集合为{1,2,3,4,5,6},边集合为{ [1,2,10],[1,3,6],[2,4,3],[2,5,9],[3,5,2],[3,6,8] }([1,2,10]中1为边的头,2为尾,10为权重)。那么需要构建如下的邻接表结构。

Paste_Image.png

<b>算法过程</b>

  1. 初始化变量和数组
    a. 声明一个顶点数目长度的boolean数组visFlag,当一个顶点被访问后,将此顶点置为true
    b. 初始化访问标识数组、前驱数组和权值数组。将visFlag中起始顶点置为true,其余元素置为false; 将所有顶点的前驱索引置为0;设置对应顶点权值,如果此点是开始顶点,其权值为0,其余设置为Integer的最大值Integer.MAX_VALUE,来表示无穷大,此值也说明这个顶点没有被访问过。
  2. 遍历邻接表,做以下操作,求出各定点离起始点最近距离
    a、找到visFlag为false并且距离D点最近的点K。
    b、将K对应的visFlag设置为true。
    c、找到K的所有邻接点,计算它们到D的距离。
    d、重复执行步骤a、b、c直至K=结束点。
  3. 获取轨迹
    a、获取结束点索引
    b、在pre中根据结束点索引找到其前驱并记录,如此直至起始点。
    c、根据b步骤求得的索引,获取对应的顶点的值,按顺序加入数组。

参考
http://www.cnblogs.com/skywang12345/p/3711516.html
代码实现
https://github.com/wangkuiwu/datastructs_and_algorithm/blob/master/source/graph/dijkstra/udg/java/ListUDG.java

相关文章

  • 空间搜索Dijkstra算法

    一、简介 一、Dijkstra算法简介参考资料http://www.cqvip.com/read/read.asp...

  • 图的最短路径

    Dijkstra算法&Floyd算法 一、Dijkstra算法 Dijkstra算法思想: 只计算v0出发到其他顶...

  • 深入解析Dijkstra's Algorithm ——

    什么是Dijkstra算法? Dijkstra算法是用来寻找最短路径最著名的算法之一。具体来说,Dijkstra算...

  • A*算法优化

    一. 概述 A算法是游戏中路径搜索的常见算法。Dijkstra是最短路径的经典算法,A算法的思路基本上和Dijks...

  • 数据结构-广度优先寻路与A星寻路算法-C#

    概述: 广度优先算法: 是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短...

  • 最短路径算法(Dijkstra)

    Dijkstra( 迪科斯特拉 )算法是用来解决单源最短路径的算法,要求路径权值非负数。该算法利用了深度优先搜索和...

  • Dijkstra 算法

    Dijkstra 算法 前言 为了达到任意两结点的最短路径,我们有几种算法可以实现:Dijkstra 算法、Flo...

  • 寻找最短路径

    这方面的经典算法,有Dijkstra算法和Floyd算法。 下面简单说一下基于Dijkstra算法略作小改动的一个...

  • 7.8图的应用:最短路径问题

    最短路径问题:Dijkstra算法 ❖解决带权最短路径问题的经典算法是以发明者命名的“Dijkstra算法”❖这是...

  • 具体算法7 - A*启发式搜索

    A* 启发式搜索算法是对 Dijkstra 算法的改进版本,它和后者的主要差别在于,加入了到终点的距离量化,使得 ...

网友评论

    本文标题:空间搜索Dijkstra算法

    本文链接:https://www.haomeiwen.com/subject/sblmrttx.html