JAVA数据结构----------Dijstra（迪杰斯特拉）图最短路径算法

算法简介

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止，是贪心算法的一种，但由于dijkstra算法主要计算从源点到其他所有点的最短路径，所以算法的效率较低。

算法思路步骤

下述代码是根据c语言改编过来的，大体思路如下

1.开始构建shortTablePath[]数组，目的是将已经知道最小的路径放入，比如shortTablePath[4] = 9，意思就是v0到v4的最短路径为9；布尔数组isgetPath[]表示该顶点是否已经找到最短路径，比如isgetPath[4] = true 表示v0到v4已经找到最小路径。

2.将邻接矩阵的第一行赋值给shortTablePath[]（将起点那行赋值给shortTablePath[]），找到数组中的最小值，例子中应该找到v1，然后把sgetPath[1] = true表示v0到v1已经找到最短路径了

3.然后找v1可以连接到的点且没找到最短路径的点即isgetPath = flase(v1可以连接到，v0也就可以间接连接到，间接连接到的点也有可能最短),比如v0——v1——v5路径为4，v0——v5路径为5，此时就将shortTablePath[5] = 4。注意的是邻接矩阵我们将两个没有联系的点权值设为1000（我想表示的是无穷大）比如最开始的时候shortTablePath[3] = 1000，即v0 ->v3权值为1000（表示无穷大）。v0->v1->v3 路径为1+7 =8 ,故shortTablePath[3] 暂时为8，

4再次找shortTablePath数组中没有找打最短路径的点中的最小值(isgetPath = flase),进行第三步操作（其实也就是2,3步骤循环，直到isgetPath 中全部为true）

算法实例

要求：求出v0点到v8（终点)的最短路径

import Graph;

/**
 * 迪杰斯特拉算法找连通图的最小权值
 * @author 65481
 *
 */
public class DnjavaDijstra {
	//顶点个数
	private final static int MAXVEX = 9;
	//最大权值
	private final static int MAXWEIGHT = 1000;
	//存放已经找到的最小权值
	private int shortTablePath[] = new int[MAXVEX];
	
	/**
	 * 获取一个图的最短路径
	 */
	public void shortesPathDijstra(Graph graph) {
		int min = 0 ;
		int  k = 0; //记录下标
		
		//顶点是否已经拿到最短路径
		boolean isgetPath[] = new boolean[MAXVEX];
		
		//初始化shortTablePath数组 使用临接矩阵的第一行
		for(int i = 0 ;i < graph.getVertexSize();i ++) {
			shortTablePath[i] = graph.getMatrix()[0][i];
		}
		
		//默认从第0点出发 起始点到起始点的最短权值为0
		shortTablePath[0] = 0;
		//起始点已经被访问过了
		isgetPath[0] = true;
		
		//一共需要循环顶点数量减1 次
		for(int i = 1;i < graph.getVertexSize();i ++) {
			//找最小值
			min = MAXWEIGHT;
			for(int j = 0 ;j < graph.getVertexSize();j ++) {
				if (shortTablePath[j] < min && !isgetPath[j]) {
					min = shortTablePath[j];
					//记录下标
					k = j;
				}
			}
			//k点已经找到了最小的权值
			isgetPath[k] = true;
			
			//更新shorttablepath
			for(int j = 0;j< graph.getVertexSize();j ++) {
				if(!isgetPath[j]&&(min + graph.getMatrix()[k][j] < shortTablePath[j])) {
					shortTablePath[j] = min + graph.getMatrix()[k][j];
				}
			}
		}
		for(int i = 0;i < graph.getVertexSize();i++) {
			System.out.println("v0到v"+i+"的最短路径为"+shortTablePath[i]);
		}
	}
	
	
	
	public static void main(String[] args) {
		DnjavaDijstra dnjavaDijstra = new DnjavaDijstra();
		Graph graph = new Graph(MAXVEX);
		
		int [] a1 = {0,1,5,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a2 = {1,0,3,7,5,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a3 = {5,3,0,MAXWEIGHT,1,7,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a4 = {MAXWEIGHT,7,MAXWEIGHT,0,2,MAXWEIGHT,3,MAXWEIGHT,MAXWEIGHT};
		int [] a5 = {MAXWEIGHT,5,1,2,0,3,6,9,MAXWEIGHT};
		int [] a6 = {MAXWEIGHT,MAXWEIGHT,7,MAXWEIGHT,3,0,MAXWEIGHT,5,MAXWEIGHT};
		int [] a7 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,3,6,MAXWEIGHT,0,2,7};
		int [] a8 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,9,5,2,0,4};
		int [] a9 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,7,4,0};
		
		graph.getMatrix()[0] = a1;
		graph.getMatrix()[1] = a2;
		graph.getMatrix()[2] = a3;
		graph.getMatrix()[3] = a4;
		graph.getMatrix()[4] = a5;
		graph.getMatrix()[5] = a6;
		graph.getMatrix()[6] = a7;
		graph.getMatrix()[7] = a8;
		graph.getMatrix()[8] = a9;
		
		dnjavaDijstra.shortesPathDijstra(graph);
	}
}
           

在上述代码中使用到了邻接矩阵表示的图，代码如下

public class Graph {
	
	//声明就是随便提一下 没定义
	private int vertexSize; //顶点数量
	private int[] vertexs;//顶点数组
	private int[][] matrix;//邻接矩阵
	private final static int MAX_WIGHT = 1000; //设置没有关系的值
	
	
	public int[][] getMatrix() {
		return matrix;
	}

	public void setMatrix(int[][] matrix) {
		this.matrix = matrix;
	}

	public static int getMaxWight() {
		return MAX_WIGHT;
	}

	public void setVertexs(int[] vertexs) {
		this.vertexs = vertexs;
	}

	public int getVertexSize() {
		return vertexSize;
	}

	public void setVertexSize(int vertexSize) {
		this.vertexSize = vertexSize;
	}

	public Graph(int vertexSize) {
	this.vertexSize = vertexSize;
	//邻接矩阵
	matrix =  new int[vertexSize][vertexSize];
	//顶点数组
	vertexs = new int[vertexSize];
	for(int i = 0;i <vertexSize;i++) {
		vertexs[i] = i; 
	}
	}

	public int[] getVertexs() {
		return vertexs;
	}


	public void setVertex(int[] vertexs) {
		this.vertexs = vertexs;
	}
}
           

运行结果如下:

v0到v0的最短路径为0

v0到v1的最短路径为1

v0到v2的最短路径为4

v0到v3的最短路径为7

v0到v4的最短路径为5

v0到v5的最短路径为8

v0到v6的最短路径为10

v0到v7的最短路径为12

v0到v8的最短路径为16