自学内容网 自学内容网

Dijkstra算法——邻接矩阵实现+路径记录

本文是在下面这篇文章的基础上做了一些补充,增加了路径记录的功能。具体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 来记录最短路径,最终打印最短路径距离和对应路劲信息。
在这里插入图片描述


原文地址:https://blog.csdn.net/hhl18730252820/article/details/135455148

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!