这里有新鲜出炉的 Java 设计模式,程序狗速度看过来!
Java 程序设计语言
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称.
这篇文章主要介绍了 java 实现最短路径算法之 Dijkstra 算法,Dijkstra 算法是最短路径算法中为人熟知的一种,是单起点全路径算法,有兴趣的可以了解一下
前言
Dijkstra 算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是 "贪心算法" 的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予 java 实现代码.
一,知识准备:1,表示图的数据结构
用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵.
图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息.
设图 G 有 n 个顶点,则邻接矩阵是一个 n*n 的方阵,定义为:
从上面可以看出,无向图的边数组是一个对称矩阵.所谓对称矩阵就是 n 阶矩阵的元满足 aij = aji.即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的.
从这个矩阵中,很容易知道图中的信息.
(1)要判断任意两顶点是否有边无边就很容易了;
(2)要知道某个顶点的度,其实就是这个顶点 vi 在邻接矩阵中第 i 行或(第 i 列)的元素之和;
(3)求顶点 vi 的所有邻接点就是将矩阵中第 i 行元素扫描一遍,arc[i][j] 为 1 就是邻接点;
而有向图讲究入度和出度,顶点 vi 的入度为 1,正好是第 i 列各数之和.顶点 vi 的出度为 2,即第 i 行的各数之和.
有向图的定义也类似,故不做赘述.
2,单起点全路径
所谓单起点全路径,就是指在一个图中,从一个起点出发,到所有节点的最短路径.
3,图论的基本知识 (读者需自行寻找相关资料)4,互补松弛条件
设标量 d1,d2,....,dN 满足
dj<=di + aij, (i,j) 属于 A,
且 P 是以 i1 为起点 ik 为终点的路,如果
dj = di + aij, 对 P 的所有边 (i, j)
成立,那么 P 是从 i1 到 ik 的最短路.其中,满足上面两式的被称为最短路问题的互补松弛条件.
二,算法思想
1,令 G = (V,E)为一个带权无向图.G 中若有两个相邻的节点, i 和 j.aij(在这及其后面都表示为下标,请注意) 为节点 i 到节点 j 的权值,在本算法可以理解为距离.每个节点都有一个值 di(节点标记) 表示其从起点到它的某条路的距离.
2,算法初始有一个数组 V 用于储存未访问节点的列表,我们暂称为候选列表.选定节点 1 为起始节点.开始时,节点 1 的 d1=0, 其他节点 di = 无穷大,V 为所有节点.
初始化条件后,然后开始迭代算法,直到 V 为空集时停止.具体迭代步骤如下:
将 d 值最小的节点 di 从候选列表中移除.(本例中 V 的数据结构采用的是优先队列实现最小值出列,最好使用斐波那契对,在以前文章有过介绍,性能有大幅提示).对于以该节点为起点的每一条边,不包括移除 V 的节点, (i, j) 属于 A, 若 dj > di + aij(违反松弛条件), 则令
dj = di + aij , (如果 j 已经从 V 中移除过,说明其最小距离已经计算出,不参与此次计算)
可以看到在算法的运算工程中,节点的 d 值是单调不增的
具体算法图解如下
三,java 代码实现
public class Vertex implements Comparable < Vertex > {
/**
* 节点名称(A,B,C,D)
*/
private String name;
/**
* 最短路径长度
*/
private int path;
/**
* 节点是否已经出列(是否已经处理完毕)
*/
private boolean isMarked;
public Vertex(String name) {
this.name = name;
this.path = Integer.MAX_VALUE; //初始设置为无穷大
this.setMarked(false);
}
public Vertex(String name, int path) {
this.name = name;
this.path = path;
this.setMarked(false);
}@Override public int compareTo(Vertex o) {
return o.path > path ? -1 : 1;
}
}
public class Graph {
/*
* 顶点
*/
private List < Vertex > vertexs;
/*
* 边
*/
private int[][] edges;
/*
* 没有访问的顶点
*/
private Queue < Vertex > unVisited;
public Graph(List < Vertex > vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
initUnVisited();
}
/*
* 搜索各顶点最短路径
*/
public void search() {
while (!unVisited.isEmpty()) {
Vertex vertex = unVisited.element();
//顶点已经计算出最短路径,设置为"已访问"
vertex.setMarked(true);
//获取所有"未访问"的邻居
List < Vertex > neighbors = getNeighbors(vertex);
//更新邻居的最短路径
updatesDistance(vertex, neighbors);
pop();
}
System.out.println("search over");
}
/*
* 更新所有邻居的最短路径
*/
private void updatesDistance(Vertex vertex, List < Vertex > neighbors) {
for (Vertex neighbor: neighbors) {
updateDistance(vertex, neighbor);
}
}
/*
* 更新邻居的最短路径
*/
private void updateDistance(Vertex vertex, Vertex neighbor) {
int distance = getDistance(vertex, neighbor) + vertex.getPath();
if (distance < neighbor.getPath()) {
neighbor.setPath(distance);
}
}
/*
* 初始化未访问顶点集合
*/
private void initUnVisited() {
unVisited = new PriorityQueue < Vertex > ();
for (Vertex v: vertexs) {
unVisited.add(v);
}
}
/*
* 从未访问顶点集合中删除已找到最短路径的节点
*/
private void pop() {
unVisited.poll();
}
/*
* 获取顶点到目标顶点的距离
*/
private int getDistance(Vertex source, Vertex destination) {
int sourceIndex = vertexs.indexOf(source);
int destIndex = vertexs.indexOf(destination);
return edges[sourceIndex][destIndex];
}
/*
* 获取顶点所有(未访问的)邻居
*/
private List < Vertex > getNeighbors(Vertex v) {
List < Vertex > neighbors = new ArrayList < Vertex > ();
int position = vertexs.indexOf(v);
Vertex neighbor = null;
int distance;
for (int i = 0; i < vertexs.size(); i++) {
if (i == position) {
//顶点本身,跳过
continue;
}
distance = edges[position][i]; //到所有顶点的距离
if (distance < Integer.MAX_VALUE) {
//是邻居(有路径可达)
neighbor = getVertex(i);
if (!neighbor.isMarked()) {
//如果邻居没有访问过,则加入list;
neighbors.add(neighbor);
}
}
}
return neighbors;
}
/*
* 根据顶点位置获取顶点
*/
private Vertex getVertex(int index) {
return vertexs.get(index);
}
/*
* 打印图
*/
public void printGraph() {
int verNums = vertexs.size();
for (int row = 0; row < verNums; row++) {
for (int col = 0; col < verNums; col++) {
if (Integer.MAX_VALUE == edges[row][col]) {
System.out.print("X");
System.out.print(" ");
continue;
}
System.out.print(edges[row][col]);
System.out.print(" ");
}
System.out.println();
}
}
}
public class Test {
public static void main(String[] args){
List<Vertex> vertexs = new ArrayList<Vertex>();
Vertex a = new Vertex("A", 0);
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
Vertex e = new Vertex("E");
Vertex f = new Vertex("F");
vertexs.add(a);
vertexs.add(b);
vertexs.add(c);
vertexs.add(d);
vertexs.add(e);
vertexs.add(f);
int[][] edges = {
{Integer.MAX_VALUE,6,3,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
{6,Integer.MAX_VALUE,2,5,Integer.MAX_VALUE,Integer.MAX_VALUE},
{3,2,Integer.MAX_VALUE,3,4,Integer.MAX_VALUE},
{Integer.MAX_VALUE,5,3,Integer.MAX_VALUE,5,3},
{Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,Integer.MAX_VALUE,5},
{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,5,Integer.MAX_VALUE}
};
Graph graph = new Graph(vertexs, edges);
graph.printGraph();
graph.search();
}
}
来源: http://www.phperz.com/article/18/0119/353062.html