本文是在下面這篇文章的基礎(chǔ)上做了一些補(bǔ)充，增加了路徑記錄的功能。具體Dijkstra的實(shí)現(xiàn)過(guò)程可以參考下面的這篇文章。
[jarvan：Dijkstra算法詳解 通俗易懂](Dijkstra算法詳解 通俗易懂 - jarvan的文章 - 知乎
https://zhuanlan.zhihu.com/p/338414118)
創(chuàng)建 GraphAdjMat 類(lèi)
GraphAdjMat 類(lèi)用來(lái)實(shí)現(xiàn)圖的鄰接矩陣，方便后續(xù)的測(cè)試，具體代碼如下：
package algorithm.graph;
import java.util.ArrayList;
import java.util.List;
public class GraphAdjMat {
private List<Integer> vertices;
private List<List<Integer>> adjMat;
/**
* 構(gòu)造函數(shù)
* @param vertices 頂點(diǎn)列表
* @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]);
}
//設(shè)置頂點(diǎn)自己到自己的權(quán)重為0
for(int i=0; i<vertices.length; i++) {
this.adjMat.get(i).set(i, 0);
}
}
public List<List<Integer>> getAdjMat() {
return this.adjMat;
}
/**
* 添加頂點(diǎn)
*/
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);
}
}
/**
* 移除頂點(diǎn)
*/
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 頂點(diǎn)1
* @param j 頂點(diǎn)2
* @param weight 邊權(quán)重
*/
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 類(lèi)中提供了增加頂點(diǎn)、移除頂點(diǎn)、增加邊和移除邊的操作。
創(chuàng)建 DijkstraAlg 類(lèi)
該類(lèi)用于實(shí)現(xiàn) Dijkstra 算法，并打印指定點(diǎn)到所有點(diǎn)的最短距離和路徑信息文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-802274.html
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}};
//構(gòu)建鄰接矩陣
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;
//開(kāi)始 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 用來(lái)確保 minIndex 頂點(diǎn)有邊，result[j] == -1 用來(lái)確保 j 點(diǎn)沒(méi)有在結(jié)果集中
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(luò)點(diǎn)的距離，或者無(wú)法到達(dá)j點(diǎn)事將新距離刷新到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;
}
}
代碼在原文代碼的基礎(chǔ)上通過(guò)增加 recordPathMap 來(lái)記錄最短路徑，最終打印最短路徑距離和對(duì)應(yīng)路勁信息。
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-802274.html
到了這里，關(guān)于Dijkstra算法——鄰接矩陣實(shí)現(xiàn)+路徑記錄的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
