迪杰斯特拉(Dijkstra)算法解决最短路径问题

Dijkstra 算法介绍

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。迪杰斯特拉(Dijkstra)算法是最经典的最短路径算法之一，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。。

最短路径问题介绍

可以将上面问题抽象为下图:

Dijkstra算法示例演示

下面开始求顶点 A 到各个顶点的最短距离

首先第一步 声明一个distance数组表示顶点A到各节点的距离编号0-8分别对应A-I顶点

顶点所对应的值为起点A到当前顶点的距离，如distance[2] = 8 即表示顶点A 到顶点C 的距离为8

将数组初始化

因为A顶点到A顶点的距离为0所以将distance[0] 的值初始化为0

其他顶点我们假设起点A到它们的距离为无穷大

继续声明一个数组already_visited表示顶点是否已经被访问

同样的0-8表示A-I 9个顶点, True表示当前节点已经被访问过 , False 表示当前节点还未被访问过

继续声明一个parent_arr 表示当前节点的父节点 即当前正在处理的节点的前一个顶点

将parent_arr[0]的值初始化为-1 ，因为节点A是第一个处理的节点 ，所以没有父节点这里用-1表示

下面开始演示Dijkstra算法的步骤

1.遍历所有未访问的节点 取距离A点距离最小的节点,此时的节点为A节点，因为只有A节点到A节点的距离为0 其他节点的距离都为无穷大

,遍历A节点的所有未访问过的子节点(即 B 和C节点) ,此时distance数组中B和C到A的距离都为无穷大,大于B和C到A的距离4和8所以将B和C到A的距离更新到distance数组即 distance[1]=4,distance[2]=8,更新B和C的父节点为A，即parent_arr[1]=0,parrent_arr[2]=0。 最后将A标记为已访问

注:红色的节点为标记为已访问的节点，蓝色节点为标记为未访问节点

2.遍历所有未标记为已访问的节点,取距离A最近的一个节点B(4),继续上一步操作,将D与A的距离distance[3]更新为distance[1]+8=12，父节点更新为parent_arr[3]=1,并将B节点标记为已访问(True) 此时C经过B到A的距离为15 比C直接到A的距离8大所以不更新C到A的距离和父节点

3.遍历所有未标记为已访问的节点，取距离A最近的节点C(8),继续上一步操作

遍历C点的子节点F,E ,F到A的距离为 distance[2]+7=15 ,因为distance[5]即F到A的距离的值此时为无穷大 所以取距离小的15更新distance[5]=15 ,同理更新E到A的距离distance[4] = 9 将E,F 的父节点标记为C 即parent_arr[5]=2,parent_arr[4]=2 并将C点标记为已访问

4.继续遍历未标记为已访问的节点，取距离A最近的节点E(9)，遍历E的所有未访问的子节点F,H

此时F点经过E,C到A的距离为:9+6=15 等于F经过C点到A点的距离15 选择不更新F到A的距离 ,也不更新F的父节点，更新H到A的距离为 9+2 = 11 将H点的父节点标记为E 即parent_arr[7]=4 并将E节点标记为已访问

5.继续遍历所有未标记为已访问的节点，取距离A最近的点H(11) ，遍历H点的所有未遍历的子节点G,I,D

G点经过H,E,C点到A点的距离为25 小于无穷大，更新distance[6]=25 ，I点经过H,E,C到A点的距离为21 更新distance[8]=21

D点经过H,E,C到A点的距离为 8+1+2+4 =15 大于 D点经过B点到A的距离 所以不更新D点到A点的距离

更新G I 的父节点为H parent_arr[6]=7 ,parent_arr[8]=7 将H标记为已访问

6.遍历所有未标记为已访问的节点,取距离A最近的节点D(12)，遍历D点的所有为访问的节点F,G

F点经过D,B到A的距离为4+8+2=14 小于当前F从C到A的值15 所以更新distance[5] = 14 .并更新F的父节点为D parent_arr[5]=3

G点经过D,B到A点的距离为 19 小于G点从H,E,C到A点的距离25 所以更新 distance[6]=19, 并更新G的父节点的D parent_arr[6]=3

将D点标记为已访问

7.遍历所有未标记为已访问的节点,取距离A最近的节点F(14)，遍历发现F已经没有子节点可以访问 所以将F标记为已访问

8.继续遍历未访问的节点，取距离A点最近的G(19) ,遍历G点所有未访问过得子节点 发现只有一个I 点

I点经过H,E,C到A点的距离为21 小于I经过G,D,B 到A的距离4+8+7+9=28 所以不更新 将G点设置为已访问

9.继续遍历未访问的节点 ，取距离A点最近的节点I(21) 遍历I点的所有子节点发现没有节点可访问

将I点标记为已访问

10.此时图中的所有节点都已经被访问至此我们得到两个数组 distance和parent_arr

distance中对应的值即为A点到相应点的最短距离

例如： A点到F点的最短距离为：distance[5] =14

A点到I点的最短距离为：distance[8]=21

那么问题来了 知道了最短路径如何得出是沿着那条路径走的呢？

这时候就要用到parrent_arr数组了

例如：求G到A的最短路径走法

从G开始 定位到parent_arr[6] 值为3 即对应的D点索引，继续定位到parent_arr[3]值为1 即B点的索引 ，定位到parent_arr[1] 值为0 即A点的索引 ，继续定位到parent_arr[0] 值为-1 结束

此时得到的路径为 G->D->B->A 倒过来A->B->D->G 即为A到G的最短路径

下面为JAVA代码实现

package com.xiaocan.dijkstra;import java.util.Arrays;public class DijkstraCase {private boolean[] already_arr; //记录那些节点已经被访问private int[] parent_arr; //记录父节点private int[] distance; //节点到起点的距离private char[] vertexes; //节点所对应的值private int[][] matrix; // 节点所对应的邻接矩阵public DijkstraCase(char[] vertexes, int[][] matrix) {this.vertexes = vertexes;this.matrix = matrix;already_arr = new boolean[vertexes.length];parent_arr = new int[already_arr.length];distance = new int[already_arr.length];}// 判断所有的所有的节点是否已经被标记public boolean IsFinished() {for (boolean b : already_arr) {if (!b) {return false;}}return true;}//返回未访问的节点中距离起点最近的节点的下标public int GetNotVisitedLeast() {int minIndex = -1;for (int i = 0; i < already_arr.length; i++) {if (!already_arr[i] && (minIndex == -1 || distance[i] < distance[minIndex])) {minIndex = i;}}return minIndex;}public void dijkstra(int from, int to) {//将起点到其他点的距离设置为一个无穷值Arrays.fill(distance, Integer.MAX_VALUE);//将所有节点设置为未访问 此步骤可以省略 因为java 中 boolean值默认为falseArrays.fill(already_arr,false);distance[from] = 0; //起点到起点的距离设置为0//起点的父节点设置为-1 表示没有父节点parent_arr[from] = -1;//检查所有的节点是否已经被标记为已访问 ,如果全部节点都被标记已访问了 则退出循环while (!IsFinished()) {//从未访问的节点中取一个离 from 起点距离最近的节点int minVertex = GetNotVisitedLeast();for (int i = 0; i < vertexes.length; i++) {/*** matrix[minVertex][i] != Integer.MAX_VALUE 表示 两个节点之前是连通的* !already_arr[i] 表示节点没有被标记为已访问* matrix[minVertex][i] + distance[minVertex]) <= distance[i] 如果当前路径距离起点的距离比 另一条路径所得到的的距离小*/if (matrix[minVertex][i] != Integer.MAX_VALUE && !already_arr[i] && (matrix[minVertex][i] + distance[minVertex]) <= distance[i] ) {//把较大的距离替换为较小的距离distance[i] = matrix[minVertex][i] + distance[minVertex];// //设置父节点parent_arr[i] = minVertex;}}//将节点设置为已访问already_arr[minVertex] = true;}System.out.println("distance="+Arrays.toString(distance)); for (int i = 1 ;i <vertexes.length;i++){StringBuilder sb = new StringBuilder();int index =i;System.out.printf("%c[%d]-->%c[%d]的最短路径距离为:%-5d" ,vertexes[from],from,vertexes[i],i,distance[i]);System.out.print("路径为:");while (index != -1) {sb.append(">-" + vertexes[index]);index = parent_arr[index];}sb.reverse();System.out.println(sb);}}public static void main(String[] args) {//表示节点的值char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};int[][] matrix = new int[vertex.length][vertex.length];final int N = Integer.MAX_VALUE; //表示一个无穷值 表示两个节点之间不连通//使用一个8x8的矩阵表示几点直接的关系 值表示 节点直接的距离//A B C D E F G H I/*A*/matrix[0] = new int[]{N, 4, 8, N, N, N, N, N, N};/*B*/matrix[1] = new int[]{4, N, 11, 8, N, N, N, N, N};/*C*/matrix[2] = new int[]{8, 11, N, N, 1, 7, N, N, N};/*D*/matrix[3] = new int[]{N, 8, N, N, N, 2, 7, 4, N};/*E*/matrix[4] = new int[]{N, N, 1, N, N, 6, N, 2, N};/*F*/matrix[5] = new int[]{N, N, 7, 2, 6, N, N, N, N};/*G*/matrix[6] = new int[]{N, N, N, 7, N, N, N, 14, 9};/*H*/matrix[7] = new int[]{N, N, N, 4, 2, N, 14, N, 10};/*I*/matrix[8] = new int[]{N, N, N, N, N, N, 9, 10, N};DijkstraCase dijkstraCase = new DijkstraCase(vertex, matrix);dijkstraCase.dijkstra(0, 8);}}

运行结果：