一、简介
一、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的距离),直至遍历到结束点。

如,若要求点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为权重)。那么需要构建如下的邻接表结构。

<b>算法过程</b>
- 初始化变量和数组
a. 声明一个顶点数目长度的boolean数组visFlag,当一个顶点被访问后,将此顶点置为true
b. 初始化访问标识数组、前驱数组和权值数组。将visFlag中起始顶点置为true,其余元素置为false; 将所有顶点的前驱索引置为0;设置对应顶点权值,如果此点是开始顶点,其权值为0,其余设置为Integer的最大值Integer.MAX_VALUE,来表示无穷大,此值也说明这个顶点没有被访问过。 - 遍历邻接表,做以下操作,求出各定点离起始点最近距离
a、找到visFlag为false并且距离D点最近的点K。
b、将K对应的visFlag设置为true。
c、找到K的所有邻接点,计算它们到D的距离。
d、重复执行步骤a、b、c直至K=结束点。 - 获取轨迹
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
网友评论