引言
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径,本篇我们学习它的一种经典算法:迪杰斯特拉算法（Dijkstra算法)。
Dijkstra算法思想
它是解决单源最短路径的贪心算法，它的思想是根据当前距离源最近的顶点Vi的迭代结果，由贪心法则运算源点到Vi的邻接顶点V[adj]的最短距离。它将顶点集合V划分为S和V-S两部分，S中的顶点到源点u的最短路径已经确定，V-S中的顶点的最短路径待定，数组dist[]存放每一次迭代的最短路径，数组p[]存放最短路径各个顶点的前驱。每一次迭代就是从S中选择最短路径的顶点t,加入集合S,然后判断与t连接的顶点j(可能不止一个)是否能够借助t作为捷径到达j,如果是捷径,则更新dist和p数组。
算法流程:
1>初始化,S={u},dist[i]=map[u][i],如果u与i相连，初始化p[i]=u,否则p[i]=-1;
2>从dist[]中找最小顶点t,加入S,V-S移除t;
3>捷径判断:V-S中所有与t相连的顶点都可以借助t到达，如果dist[t]+map[t][j]<dist[j]，则表示邻接点j可以经过t走捷径,更新dist[j]=dist[t]+map[t][j],和前驱p[j]=t;
4>重复执行1,2,3步骤,知道V-S为空。
具体的图解流程参考《趣学算法》的最小路径小节，或者这篇博客。
Dijkstra算法实现
package graphic;
import stack.Stack;
/**
* Created by chenming on 2018/6/15
* 迪科斯彻最短路径算法
*/
public class Dijkstra {
private int[][] map;//路径图的邻接矩阵描述，顶点位置默认为索引
private int n;//顶点个数
public final static int INF = Integer.MAX_VALUE;
private int[] dist;//dist[j]存放顶点j到源顶点的最短距离
private boolean[] flg;//flg[j]=true表明该顶点的最短路径已经算出，加入集合S。
private int[] p;//保存最短路径上的前驱顶点，p[i] = j表示顶点i的前驱顶点为j
public Dijkstra(int[][] map) {
if (map == null || map.length == 0) {
throw new RuntimeException("图不能为空");
}
this.map = map;
n = this.map.length;
}
/**
* 最短路径迭代算法
*
* @param u 源顶点
*/
public void dijkstra(int u) {
//step1.初始化
dist = new int[n];
flg = new boolean[n];
p = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = map[u][i];//初始化为u的邻接点路径数组
flg[i] = false;
if (dist[i] == INF) {
p[i] = -1;
} else {
p[i] = u;
}
}
dist[u] = 0;//u到u的距离为0
p[u] = -1;//u的前驱初始化为-1
flg[u] = true;//初始化S只有一个顶点u
//step2.找最小值
for (int i = 0; i < n; i++) {
int t = u;//当前路径的最小的顶点
int min = INF;
//从V-S集合中寻找最小值
for (int j = 0; j < n; j++) {
if (!flg[j] && dist[j] < min) {
min = dist[j];
t = j;
}
}
if (t == u) {//没找到最小值,直接返回
return;
}
//将t加入集合S
flg[t] = true;
//根据这个最小顶点，判断V-S集合中的顶点能否借助它实现"捷径",如果能则更新dist和路径前驱
for (int j = 0; j < n; j++) {
//dist[t] + map[t][j] 为从经过t，到j的路径
boolean isShortter = dist[j] > dist[t] + map[t][j];//借助t的捷径是否生效
boolean isConnected = map[t][j] > 0 && map[t][j] < INF;//t与j是否相连
if (!flg[j] && isShortter && isConnected) {
//更新dist
dist[j] = dist[t] + map[t][j];
//更新前驱
p[j] = t;
}
}
}
}
/**
* 打印最短距离
*/
public void dumpDistShortestTable() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(dist[i] + ",");
}
System.out.println(sb.toString());
}
/**
* 打印最短路径上的前驱节点
*/
public void dumpDistShortestPath() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(p[i] + ",");
}
System.out.println(sb.toString());
}
/**
* 打印从源节点到目标节点的路径
* p中存的是前驱节点，因此需要引入栈来存放从源点到目标的路径
* @param distIndex
*/
public void dumpShortestPatnToDist(int distIndex){
Stack<Integer> stack = new Stack<>();
stack.push(distIndex);
int preIndex = p[distIndex];
while (preIndex != -1){
stack.push(preIndex);
preIndex = p[preIndex];
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
Integer p = stack.pop();
if(p != null){
sb.append(p+" ");
}
}
System.out.println("到达目标:"+distIndex + " 的最短路径为:"+sb.toString()+", 路径长为:"+dist[distIndex]);
}
}
说明:由于p[]保存的是各个顶点的前驱索引,所以打印从源节点到目标节点的路径时需要引入栈。
测试图结构、代码和结果如下:
最短路径测试图.png
/**
* 创建路径图
*/
public Dijkstra createGraph(){
//创建代码写的很随意，仅做测试，别效仿！
int [] a1 = new int[]{0,1,5, Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF};
int [] a2 = new int[]{1,0,3,7,5,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF};
int [] a3 = new int[]{5,3,0,Dijkstra.INF,1,7,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF};
int [] a4 = new int[]{Dijkstra.INF,7,Dijkstra.INF,0,2,Dijkstra.INF,3,Dijkstra.INF,Dijkstra.INF};
int [] a5 = new int[]{Dijkstra.INF,5,1,2,0,3,6,9,Dijkstra.INF};
int [] a6 = new int[]{Dijkstra.INF,Dijkstra.INF,7,Dijkstra.INF,3,0,Dijkstra.INF,5,Dijkstra.INF};
int [] a7 = new int[]{Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,3,6,Dijkstra.INF,0,2,7};
int [] a8 = new int[]{Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,9,5,2,0,4};
int [] a9 = new int[]{Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,Dijkstra.INF,7,4,0};
int[][] matrix= new int[9][9];
matrix[0] = a1;
matrix[1] = a2;
matrix[2] = a3;
matrix[3] = a4;
matrix[4] = a5;
matrix[5] = a6;
matrix[6] = a7;
matrix[7] = a8;
matrix[8] = a9;
Dijkstra map = new Dijkstra(matrix);
return map;
}
@Test
public void testDijkstra(){
Dijkstra map = createGraph();
map.dijkstra(0);
for(int i = 0; i < 9; i++){
map.dumpShortestPatnToDist(i);
}
}
测试结果:
到达目标:0 的最短路径为:0 , 路径长为:0
到达目标:1 的最短路径为:0 1 , 路径长为:1
到达目标:2 的最短路径为:0 1 2 , 路径长为:4
到达目标:3 的最短路径为:0 1 2 4 3 , 路径长为:7
到达目标:4 的最短路径为:0 1 2 4 , 路径长为:5
到达目标:5 的最短路径为:0 1 2 4 5 , 路径长为:8
到达目标:6 的最短路径为:0 1 2 4 3 6 , 路径长为:10
到达目标:7 的最短路径为:0 1 2 4 3 6 7 , 路径长为:12
到达目标:8 的最短路径为:0 1 2 4 3 6 7 8 , 路径长为:16
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
网友评论