前言
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();
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问， 点击进行留言回复！！
详解SpringBoot修改启动端口server.port的四种方式
网友评论