原理与普里母算法思路相同，只是比较的时候不同
通过邻接矩阵进行计算
-
算法准备
a. 邻接矩阵
b. 最小权值数组least
c. 上一个顶点下标数组lastIndex
d. 最小权值和sum
-
算法思路
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;
}
}
