1. 应用场景:
假如有七个村庄(ABCDEFG),有个人从G点出发,到其他六个村庄的最短路径分别是多少?到A、B、F、E只有一条路,没得选,但是到C有两条路,可以是2 + 7
,也可以是8 + 4
,到D点可以是3 + 9
,也可以是6 + 4
。图上标明了距离我们当然一看就知道怎么选,那么如何能让程序选择最短的路径呢?
最短路径问题
迪杰斯特拉算法就是求最短路径的经典算法。它的主要思想就是以起始点向外层层扩展,用广度优先的思想,直到扩展到终点为止。
2. 算法步骤:
以上面的例子,从G开始处理,来讲解这个过程:
String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
A B C D E F G
A{N, 5, 7 ,N, N, N, 2}
B{5, N, N ,9, N, N, 3}
C{7, N, N ,N, 8, N, N}
D{N, 9, N ,N, N, 4, N}
E{N, N, 8 ,N, N, 5, 4}
F{N, N, N ,4, 5, N, 6}
G{2, 3, N ,N, 4, 6, N}
already_arr
,长度为顶点的个数。数组里面,0表示未访问过该顶点,1表示访问过该顶点。初始的时候其他都是0,G顶点的是1。int[] already_arr = {0, 0, 0, 0, 0, 0, 1};
dis
,长度也是顶点的个数。该数组记录的是当前顶点到其他顶点的距离,初始的时候是一个较大的数,到自己的距离就是0。int[] dis = {N, N, N, N, N, N, 0};
pre_visited
,长度也是顶点的个数。数组表示顶点的到前驱顶点的距离,初始时候都是0。int[] pre_visited = {0, 0, 0, 0, 0, 0, 0};
dis
数组,如下:int[] dis = {2, 3, N, N, 4, 6, 0};
pre_visited
数组变成了:int[] pre_visited = {6, 6, 0, 0, 6, 6, 0};
dis
数组中。3. 代码实现:
class Graph{
String[] vertexs; // 存放顶点
int[][] edges; // 邻接矩阵,存放边
public Graph(String[] vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
}
}
class VisitedVertex{
private static final int N = 999;
public int[] already_arr;
public int[] pre_visited;
public int[] dis;
/**
* 构造器
* @param length 顶点的个数
* @param index 出发点的索引
*/
public VisitedVertex(int length, int index) {
this.already_arr = new int[length];
this.pre_visited = new int[length];
this.dis = new int[length];
// 初始化dis数组
Arrays.fill(dis, N);
dis[index] = 0;
}
/**
* 判断index对应的顶点是否被访问过
* @param index
* @return
*/
public boolean isVisited(int index) {
return already_arr[index] == 1;
}
/**
* 更新dis数组,索引为index的值更新为len
* @param index
* @param len
*/
public void updateDis(int index, int len) {
dis[index] = len;
}
/**
* 更新前驱顶点
* @param index
* @param val
*/
public void updatePre(int index, int val) {
pre_visited[index] = val;
}
/**
* 将index设置为已访问
* @param index
*/
public void updateAlreadyArr(int index) {
already_arr[index] = 1;
}
/**
* 返回出发顶点到index这个顶点的距离
* @param index
* @return
*/
public int getDis(int index) {
return dis[index];
}
/**
* 返回要处理的下一个顶点
* @return
*/
public int nextVertexs() {
int index = 0;
int min = N;
for (int i=0; i< already_arr.length; i++) {
if (!isVisited(i) && dis[i] < min) {
min = dis[i];
index = i;
}
}
updateAlreadyArr(index);
return index;
}
public void printArr() {
System.out.println(Arrays.toString(this.dis) + " dis");
System.out.println(Arrays.toString(this.pre_visited) + " pre_visited");
System.out.println(Arrays.toString(this.already_arr) + " already_arr");
}
}
/**
* 迪杰斯特拉算法实现
* @param index 出发顶点的下标
*/
public void dsj(int index) {
VisitedVertex visitedVertex = new VisitedVertex(this.vertexs.length, index);
updateArrs(index, visitedVertex);
// 下一个要处理的顶点
for (int i=1; i<vertexs.length; i++) {
index = visitedVertex.nextVertexs();
updateArrs(index, visitedVertex);
}
visitedVertex.printArr();
}
/**
* 拿到邻接矩阵的第index行,根据这一行对三个数组进行更新
* @param index
* @param visitedVertex
*/
private void updateArrs(int index, VisitedVertex visitedVertex) {
int[] tempArr = this.edges[index];
// distance表示出发顶点到索引为index的这个顶点的距离
int distance = 0;
for (int i=0; i< tempArr.length; i++) {
// 先前的距离 + 本次遍历得到的距离
distance = visitedVertex.getDis(index) + tempArr[i];
if (distance < visitedVertex.getDis(i) && !visitedVertex.isVisited(i)) {
visitedVertex.updateDis(i, distance);
visitedVertex.updatePre(i, index);
visitedVertex.updateAlreadyArr(index);
}
}
}
测试方法:
public class DijkstraDemo {
public static final int N = 999;
public static void main(String[] args) {
String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
int[][] edges = {
{N, 5, 7 ,N, N, N, 2},
{5, N, N ,9, N, N, 3},
{7, N, N ,N, 8, N, N},
{N, 9, N ,N, N, 4, N},
{N, N, 8 ,N, N, 5, 4},
{N, N, N ,4, 5, N, 6},
{2, 3, N ,N, 4, 6, N}
};
Graph graph = new Graph(vertexs, edges);
graph.dsj(6);
}
}
运行后得到结果如下:
运行结果
dis
数组就是我们想要的结果,即对应的顶点G到各个点的最短距离。