本文是在下面这篇文章的基础上做了一些补充，增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。
[jarvan：Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎
https://zhuanlan.zhihu.com/p/338414118)
创建 GraphAdjMat 类
GraphAdjMat 类用来实现图的邻接矩阵，方便后续的测试，具体代码如下：
package algorithm.graph;
import java.util.ArrayList;
import java.util.List;
public class GraphAdjMat {
private List<Integer> vertices;
private List<List<Integer>> adjMat;
/**
* 构造函数
* @param vertices 顶点列表
* @param edges 边
*/
public GraphAdjMat(int[]vertices, int[][]edges) {
this.vertices = new ArrayList<>();
this.adjMat = new ArrayList<>();
for(int v : vertices) {
addVertex(v);
}
for(int[]e : edges) {
addEdge(e[0],e[1],e[2]);
}
//设置顶点自己到自己的权重为0
for(int i=0; i<vertices.length; i++) {
this.adjMat.get(i).set(i, 0);
}
}
public List<List<Integer>> getAdjMat() {
return this.adjMat;
}
/**
* 添加顶点
*/
public void addVertex(int val) {
int n = vertices.size();
vertices.add(val);
List<Integer> newRow = new ArrayList<>();
for(int i=0; i<n; i++) {
newRow.add(-1);
}
adjMat.add(newRow);
for(List<Integer> row : adjMat) {
row.add(-1);
}
}
/**
* 移除顶点
*/
public void removeVertex(int index) {
if(index < 0 || index >= vertices.size()) {
throw new IndexOutOfBoundsException();
}
vertices.remove(index);
adjMat.remove(index);
for(List<Integer> row : adjMat) {
row.remove(index);
}
}
/**
* 添加边
* @param i 顶点1
* @param j 顶点2
* @param weight 边权重
*/
public void addEdge(int i, int j, int weight) {
if(i<0||j<0||i>=vertices.size()||j>=vertices.size()||i==j) {
throw new IndexOutOfBoundsException();
}
adjMat.get(i).set(j, weight);
adjMat.get(j).set(i, weight);
}
/**
* 移除边
*/
public void removeEdge(int i, int j) {
if(i<0||j<0||i>=vertices.size()||j>=vertices.size()||i==j) {
throw new IndexOutOfBoundsException();
}
adjMat.get(i).set(j, -1);
adjMat.get(j).set(i, -1);
}
public void print() {
System.out.println("adj mat:");
for(List<Integer> row : adjMat) {
for(int v : row) {
System.out.printf("%3d", v);
}
System.out.println();
}
}
}
GraphAdjMat 类中提供了增加顶点、移除顶点、增加边和移除边的操作。
创建 DijkstraAlg 类
该类用于实现 Dijkstra 算法，并打印指定点到所有点的最短距离和路径信息
package algorithm.graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Dijkstra 算法
*/
public class DijkstraAlg {
public static void main(String[]args) {
char[]vertexNames = {
'A','B','C','D'};
int[]vertices = {
1,2,3,4};
int[][]edges = {
{
0,1,1},{
0,3,6},{
1,2,4},{
1,3,1},{
2,3,1}};
//构建邻接矩阵
GraphAdjMat adjMat = new GraphAdjMat(vertices, edges);
adjMat.print();
int startVertex = 0;
List<ShortestPath> result = dijkstra(adjMat.getAdjMat(),startVertex);
System.out.println("dijkstra result: ");
for(int i=0; i<vertexNames.length; i++) {
System.out.printf("%3s -> %s distence : %d ; ",vertexNames[startVertex], vertexNames[i], result.get(i).distence);
List<Integer> path = result.get(i).path;
System.out.print("A -> ");
for(int j=0; j<path.size(); j++) {
if(j < path.size()-1) {
System.out.printf("%s -> ",vertexNames[path.get(j)]);
}else {
System.out.printf("%s\n", vertexNames[path.get(j)]);
}
}
}
}
public static List<ShortestPath> dijkstra(List<List<Integer>> graph, int startVertex) {
int len = graph.size();
List<ShortestPath> result = new ArrayList<>(len);
int[]notFound = new int[len];
//初始化 result
for(int i=0; i<len; i++) {
ShortestPath shortestPath = new ShortestPath();
shortestPath.distence = -1;
shortestPath.path = new ArrayList<>();
result.add(i, shortestPath);
}
ShortestPath startVertexPath = new ShortestPath();
startVertexPath.distence = 0;
startVertexPath.path = new ArrayList<>(0);
result.set(startVertex,startVertexPath);
//初始化 notFound
for(int i=0; i<len; i++) {
notFound[i] = graph.get(startVertex).get(i);
}
notFound[startVertex] = -1;
//开始 Dijkstra 算法
Map<Integer,List<Integer>> recordPathMap = new HashMap<>();
for(int i=1; i<len; i++) {
int min = Integer.MAX_VALUE;
int minIndex = 0;
for(int j=0; j<len; j++) {
if(notFound[j] > 0 && notFound[j] < min) {
min = notFound[j];
minIndex = j;
}
}
result.get(minIndex).distence = min;
notFound[minIndex] = -1;
//刷新 notFound
for(int j=0; j<len; j++) {
//graph.get(minIndex).get(j) > 0 用来确保 minIndex 顶点有边，result[j] == -1 用来确保 j 点没有在结果集中
if(graph.get(minIndex).get(j) > 0 && result.get(j).distence == -1) {
int newDistence = result.get(minIndex).distence + graph.get(minIndex).get(j);
//计算合并距离如果小于直接到j点的距离，或者无法到达j点事将新距离刷新到notFound中
if(newDistence < notFound[j] || notFound[j] == -1) {
notFound[j] = newDistence;
if(!recordPathMap.containsKey(j)) {
List<Integer> tempList = new ArrayList<>(1);
tempList.add(minIndex);
recordPathMap.put(j, tempList);
}else {
recordPathMap.get(j).add(minIndex);
}
}
}
}
}
System.out.println(recordPathMap);
//推到路径
for(int i=0; i<len; i++) {
result.get(i).path.addAll(recordPathMap.getOrDefault(i, new ArrayList<>()));
result.get(i).path.add(i);
}
return result;
}
public static void printArr(int[]arr, String arrName) {
System.out.print(arrName);
for(int i : arr) {
System.out.printf("%3d", i);
}
System.out.println();
}
static class ShortestPath {
public int distence;
public List<Integer> path;
}
}
代码在原文代码的基础上通过增加 recordPathMap 来记录最短路径，最终打印最短路径距离和对应路劲信息。
