这篇文章主要介绍了java实现最短路径算法之Dijkstra算法算法的示例,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获、下面让小编带着大家一起了解一下。
<强>一、知识准备:
<强> 1,表示图的数据结构
用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵。
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点,则邻接矩阵是一个n * n的方阵,定义为:
从上面可以看的出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij=这个地方。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。
从这个矩阵中,很容易知道图中的信息。
(1)要判断任意两顶点是否有边无边就很容易了。
(2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第我行或(第我列)的元素之和;
(3)求顶点vi的所有邻接点就是将矩阵中第我行元素扫描一遍,弧[我][j]为1就是邻接点;
而有向图讲究入度和出度,顶第六点的入度为1,正好是我第列各数之和。顶点vi的出度为2,即第行我的各数之和。
有向图的定义也类似,故不做赘述。
<强> 2,单起点全路径
所谓单起点全路径,就是指在一个图中,从一个起点出发,到所有节点的最短路径只
<强> 3,图论的基本知识(读者需自行寻找相关资料)
<强> 4,互补松弛条件
设标量d1, d2, ...., dN满足
dj<=di + aij,,(i, j)属于,
且p是以i1为起点本土知识为终点的路,如果
dj=di + aij,对p的所有边(i, j)
成立,那么p是从i1到本土知识的最短路。其中,满足上面两式的被称为最短路问题的互补松弛条件。
<强>二,算法思想
1,令G=(V, E)为一个带权无向图.G中若有两个相邻的节点,我和j.aij(在这及其后面都表示为下标,请注意)为节点我到节点j的权值,在本算法可以理解为距离。每个节点都有一个值di(节点标记)表示其从起点到它的某条路的距离。
2,算法初始有一个数V组用于储存未访问节点的列的表,我们暂称为候选列表。选定节点1为起始节点。开始时,节点1的d1=0,其他节点di=无穷大,V为所有节点。
初始化条件后,然后开始迭代算法,直到V为空集时停止。具体迭代步骤如下:
将d值最小的节点di从候选列表中移除。(本例中V的数据结构采用的是优先队列实现最小值出列,最好使用斐波那契对,在以前文章有过介绍,性能有大幅提示)。对于以该节点为起点的每一条边,不包括移除V的节点,(i, j)属于,若dj祝辞di + aij(违反松弛条件),则令
dj=di + aij ,,(如果j已经从V中移除过,说明其最小距离已经计算出,不参与此次计算)
可以看到在算法的运算工程中,节点的d值是单调不增的
具体算法图解如下
<强>三、java代码实现
