【迪杰斯特拉】基本原理-Java实现
2020-07-11 本文已影响0人
bangbang2
迪杰斯特拉求的是起始点到其他各个点的最短的距离
基本原理如下（看图就行），N个节点得迭代N-1轮，因为起始点自己不用迭代：
image.png
每一轮迭代的主要做法：
（1）：在U数组找最短距离，其中U数组来保存当前起始点到各个点的最短距离
代码如下：
//第二步，在U数组选取距离最短的边
int min = MAX_WEIGHT;
for (int j = 0; j < vertexes.length; j++) {
//如果
if (flag[j] == false && U[j] < min) {
min = U[j];
k = j;//此时的k代表选中的最短距离的点
}
}
（2）：找到最短距离，选中该距离涉及到的另一个点，将该点的Flag置为true，代表该节点已经被选中，已经加入S数组，S数组来保留已经求出最小距离的节点
//将k放入S中
S[i] = vertexes[k];//选中一个点
//将选中节点置为true，代表已经被选中
flag[k] = true;
（3）：在加入上述该点后，更新U数组的全部最短距离，如果找到一个更小的距离就更新
//在上一步，选取好一个最短距离的节点后，开始更新加入这个节点后，起始点对其他所有节点的最新
//距离
for (int j = 0; j < vertexes.length; j++) {
//要求起始点到j点的最短距离，已经加入k节点，我们先找k节点到j节点是不是无穷大，如果不是无穷大就更新
//距离
int tmp = (matrix[k][j] == MAX_WEIGHT ? MAX_WEIGHT : (min + matrix[k][j]));
if (flag[j] == false && (tmp < U[j])) {//如果刚找到的距离小于已知起始点到j的距离
//说明还有最优解，就对它更新
U[j] = tmp;
//那j节点的前一个节点就是k了
prev[j] = k;
}
}
输出结果如下：
image.png
详细的看代码的步骤:
package 迪杰斯特拉;
import java.util.ArrayList;
public class ShortestPathDijkstra {
/** 邻接矩阵 */
private int[][] matrix;
/** 表示正无穷 */
private int MAX_WEIGHT = Integer.MAX_VALUE;
/** 顶点集合 */
private String[] vertexes;
/**
* 创建图2
*/
private void createGraph2(int index) {
matrix = new int[index][index];
vertexes = new String[index];
int[] v0 = { 0, 1, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
int[] v1 = { 1, 0, 3, 7, 5, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
int[] v2 = { 5, 3, 0, MAX_WEIGHT, 1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
int[] v3 = { MAX_WEIGHT, 7, MAX_WEIGHT, 0, 2, MAX_WEIGHT, 3, MAX_WEIGHT, MAX_WEIGHT };
int[] v4 = { MAX_WEIGHT, 5, 1, 2, 0, 3, 6, 9, MAX_WEIGHT };
int[] v5 = { MAX_WEIGHT, MAX_WEIGHT, 7, MAX_WEIGHT, 3, 0, MAX_WEIGHT, 5, MAX_WEIGHT };
int[] v6 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 3, 6, MAX_WEIGHT, 0, 2, 7 };
int[] v7 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 5, 2, 0, 4 };
int[] v8 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 7, 4, 0 };
matrix[0] = v0;
matrix[1] = v1;
matrix[2] = v2;
matrix[3] = v3;
matrix[4] = v4;
matrix[5] = v5;
matrix[6] = v6;
matrix[7] = v7;
matrix[8] = v8;
vertexes[0] = "v0";//每一个节点
vertexes[1] = "v1";
vertexes[2] = "v2";
vertexes[3] = "v3";
vertexes[4] = "v4";
vertexes[5] = "v5";
vertexes[6] = "v6";
vertexes[7] = "v7";
vertexes[8] = "v8";
}
/**
* 创建图1
*/
private void createGraph1(int index) {
matrix = new int[index][index];
vertexes = new String[index];
int[] v0 = { 0, 1, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT };
int[] v1 = { 1, 0, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
int[] v2 = { MAX_WEIGHT, 1, 0, 1, MAX_WEIGHT, MAX_WEIGHT };
int[] v3 = { MAX_WEIGHT, MAX_WEIGHT, 1, 0, 1, MAX_WEIGHT };
int[] v4 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, 0, 1 };
int[] v5 = { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, 1, 0 };
matrix[0] = v0;
matrix[1] = v1;
matrix[2] = v2;
matrix[3] = v3;
matrix[4] = v4;
matrix[5] = v5;
vertexes[0] = "A";
vertexes[1] = "B";
vertexes[2] = "C";
vertexes[3] = "D";
vertexes[4] = "E";
vertexes[5] = "F";
}
/**
* Dijkstra最短路径。
*
* vs -- 起始顶点(start vertex) 即，统计图中"顶点vs"到其它各个顶点的最短路径。
*/
public void dijkstra(int vs) {
// flag[i]=true表示"顶点vs"到"顶点i"的最短路径已成功获取
boolean[] flag = new boolean[vertexes.length];
// U[i]，代表起始点到点i的最短的距离，初始为起始点到各点的距离
int[] U = new int[vertexes.length];
// 前驱顶点数组,即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。
int[] prev = new int[vertexes.length];
// S的作用是记录已求出最短路径的顶点
String[] S = new String[vertexes.length];
//对以下的元素进行初始化，U数组用起始点到其他点的直接距离来初始化，直接距离代表不经过第三个点
for (int i = 0; i < vertexes.length; i++) {
flag[i] = false; //所有的点都设置为未经过
U[i] = matrix[vs][i];
prev[i] = 0;//每一个节点的前置节点都为0，0代表起始节点
}
flag[vs] = true;//vs代表起始节点，起始节点被选中
U[vs] = 0;//自己到自己肯定是0
S[0] = vertexes[vs];//将节点名字加入S数组
int k = 0;//临时记录节点
for (int i = 1; i < vertexes.length; i++) {//i代表的不是节点，而是
//第几轮，从图片中可得，有n个节点，需要迭代n-1轮，因为起始点不用找最小值，迭代一轮需一个节点
//加入到S数组
//第二步，在U数组选取距离最短的边
int min = MAX_WEIGHT;
for (int j = 0; j < vertexes.length; j++) {
//如果
if (flag[j] == false && U[j] < min) {
min = U[j];
k = j;//此时的k代表选中的最短距离的点
}
}
//将k放入S中
S[i] = vertexes[k];//选中一个点
//将选中节点置为true，代表已经被选中
flag[k] = true;
//在上一步，选取好一个最短距离的节点后，开始更新加入这个节点后，起始点对其他所有节点的最新
//距离
for (int j = 0; j < vertexes.length; j++) {
//要求起始点到j点的最短距离，已经加入k节点，我们先找k节点到j节点是不是无穷大，如果不是无穷大就更新
//距离
int tmp = (matrix[k][j] == MAX_WEIGHT ? MAX_WEIGHT : (min + matrix[k][j]));
if (flag[j] == false && (tmp < U[j])) {//如果刚找到的距离小于已知起始点到j的距离
//说明还有最优解，就对它更新
U[j] = tmp;
//那j节点的前一个节点就是k了
prev[j] = k;
}
}
}
//打印结果
System.out.println("起始顶点：" + vertexes[vs]);
for (int i = 0; i < vertexes.length; i++) {
System.out.print("最短路径（" + vertexes[vs] + "," + vertexes[i] + "):" + U[i] + " ");
ArrayList<String> path = new ArrayList<>();//其实和数组也一样
int j = i;
while (true) {//倒序加入arraylist，先将终点加入，然后利用prev数组找到
//站点的下一个节点，一个一个的回溯到起始点
path.add(vertexes[j]);
if (j == 0)//如果遇到起始点就跳出循环
break;
j = prev[j];
}
for (int x = path.size()-1; x >= 0; x--) {//倒序输出
if (x == 0) {
System.out.println(path.get(x));
} else {
System.out.print(path.get(x) + "->");
}
}
}
System.out.println("顶点放入S中的顺序：");//按S数组的顺序输出即可
for (int i = 0; i< vertexes.length; i++) {
System.out.print(S[i]);
if (i != vertexes.length-1)
System.out.print("-->");
}
}
public static void main(String[] args) {
ShortestPathDijkstra dij = new ShortestPathDijkstra();
dij.createGraph1(6);
// dij.createGraph2(9);
dij.dijkstra(0);
}
}
