数据结构图Graph之最短路径问题迪杰斯特拉算法

Posted by Naah on Thursday, Aug 17,2017 11:36:06

原理与普里母算法思路相同,只是比较的时候不同

通过邻接矩阵进行计算

  1. 算法准备

    a. 邻接矩阵

    b. 最小权值数组least

    c. 上一个顶点下标数组lastIndex

    d. 最小权值和sum

  2. 算法思路

    a. 将least数组初始化为邻接矩阵中第一个节点的出度数组

    b. 开始循环

    c. for循环least数组中最小的值,记录为min,并记录下标为minIndex

    d. 输出度的信息,累加min到sum

    e. for遍历minIndex数组中的权值

    f. Least数组中入度的权值加出度权值小于least数组中的权值时,或least数组中不连通,而此时连通时

    g. 将该权值覆盖到least数组中的位置

    h. 设置lastIndex该位置为minIndex

public class Graph> {

	// 顶点数组
	private T[] vertexs;

	// 邻接表元素数组
	private VertexNeighborNode[] neighborArray;

	// 邻接矩阵
	private int[][] matrix;

	// 泛型对象的类文件
	private Class Class;

	// 顶点数量
	private int size;

	// 常亮:未连接
	public static final int NO_LINK = -1;

	/**
	 * 构造方法
	 * @param Class 类对象
	 * @param vertexs 顶点可选数组
	 */
	public Graph(Class<T> Class, T... vertexs) {
		super();
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.Class = Class;

	}

	/**
	 * 构造方法
	 * @param vertexs 可选数组
	 */
	public Graph(T... vertexs) {
		super();
		this.vertexs = vertexs;
		this.size = vertexs.length;

	}


	/**
	 * 得到邻接矩阵
	 * @return
	 */
	public int[][] getMatrix() {
		return matrix;
	}

	/**
	 * 设置邻接矩阵
	 * @param matrix 邻接矩阵
	 * @throws Exception 数组长度不对
	 */
	public void setMatrix(int[][] matrix) throws Exception {
		if (matrix.length != this.vertexs.length) {
			throw new Exception("二维数组长度不对");
		}
		for (int i = 0; i < matrix.length; i++) {
			if (matrix[i].length != this.vertexs.length) {
				throw new Exception("二维数组长度不对");
			}

		}
		this.matrix = matrix;
	}

/**
	 * 最短路径-迪杰特斯拉算法
	 * @param v 下标
	 * @return 最小路径数组
	 * @throws Exception
	 */
	public int[] dijstra(int v) throws Exception {

		//如果链接矩阵为空,则
		if (matrix == null) {

			//抛出异常
			throw new Exception("未找到邻接矩阵");
		}

		//创建最短路径数组
		int[] least = new int[size];

		//创建记录数组
		boolean[] getLeastWeight = new boolean[size];
		int k = 0;

		//初始化最短路径数组
		for (int i = 0; i < least.length; i++) {
			least[i] = matrix[v][i];

		}

		//将当前下标记录
		getLeastWeight[v] = true;

		//循环找出最短路径
		for (int i = 0; i < least.length; i++) {

			//将最小值赋值
			int min = Integer.MAX_VALUE;

			//循环查找最小的权值,并暂时保存下标
			for (int j = 0; j < least.length; j++) {
				if (!getLeastWeight[j] && least[j] > 0 && least[j] < min) {
					min = least[j];
					k = j;
				}
			}

			//将该顶点记录
			getLeastWeight[k] = true;

			//循环最小权值的顶点,如果有比上一个顶点到那个顶点权值更小,则将更小的权值赋值
			for (int j = 0; j < getLeastWeight.length; j++) {
				if (!getLeastWeight[j] && ((matrix[k][j] + min < least[j]
						&& matrix[k][j] > 0)
						|| (least[j] == NO_LINK && matrix[k][j] != NO_LINK))) {
					least[j] = matrix[k][j] + min;
				}
			}
		}

		//返回最小路径数组
		return least;

}


}