Java利用Dijkstra和Floyd分別求取圖的最短路徑
更新時間：2022年01月25日 15:54:17 作者：劉Java
本文主要介紹了圖的最短路徑的概念，并分別利用Dijkstra算法和Floyd算法求取最短路徑，最后提供了基于鄰接矩陣和鄰接表的圖對兩種算法的Java實現(xiàn)。需要的可以參考一下
本文詳細介紹了圖的最短路徑的概念，然后介紹了求最短路徑的兩種算法：Dijkstra算法和Floyd算法的原理，最后提供了基于鄰接矩陣和鄰接表的圖對兩種算法的Java實現(xiàn)。
閱讀本文需要一定的圖的基礎(chǔ)，如果對于圖不是太明白的可以看看這篇文章：Java數(shù)據(jù)結(jié)構(gòu)之圖的原理與實現(xiàn)。
1 最短路徑的概述
在生活中，圖形結(jié)構(gòu)的應(yīng)用是最廣泛的。比如常見的交通路線選擇，站點可以看作頂點，站點之間如果有路徑，則算作兩點之間的邊或者弧，站點之間的通行時間，可以看作邊或者弧的權(quán)值。
上圖就是生活中出行路線的選擇映射到圖形結(jié)構(gòu)的案例。頂點作為站點，站點之間能夠到達則擁有邊，站點的之間的通行時間則是邊的權(quán)值。
對于出行路線的選擇，不同的人有不同的選擇。其中有一種很常見的選擇是要求出發(fā)地和目的地之間的總通行時間最短，而不在乎中途到底有幾站。畢竟通行時間對于很多人來說是寶貴的！
這樣的問題轉(zhuǎn)轉(zhuǎn)換為數(shù)學模型，就是求帶權(quán)圖的最短路徑，就是求帶權(quán)圖形兩頂點之間的權(quán)值最小的路徑。即如果從圖中某一頂點（源點）到達另一頂點（終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權(quán)值總和（稱為路徑長度）達到最小。
實際上最短路徑有兩重含義，一個兩頂點之間的路徑數(shù)量最少，另一個是兩頂點之間的路徑距離最短，本次主要解決路徑距離最短的問題，即最小權(quán)值和。常見的解決算法一般是兩種，迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd)算法。
2 杰斯特拉（Dijkstra）算法
2.1 原理
迪杰斯特拉（Dijkstra）算法是由荷蘭計算機科學家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是尋找給定的加權(quán)圖中指定頂點間最短路徑問題的算法
Dijkstra算法并不是一下子就求出了起點到終點的最短路徑，而是采用的是貪心算法策略，一步步求出它們之間頂點的最短路徑，過程中都是基于已經(jīng)求出的最短路徑的基礎(chǔ)上，求得更遠頂點的最短路徑，最終得到起點和終點的最短路徑。
通用步驟如下：
1.指定兩個集合S和U。S的作用是記錄已求出最短路徑的頂點，而U則是記錄還未求出最短路徑的頂點，以及這些頂點到起始頂點的權(quán)。
2.指定一個起始頂點A，存入集合S中，其他頂點以及到頂點A的權(quán)存入集合U中，從U中找出并移除路徑最短的頂點B，并將其加入到S中，并且更新U中對應(yīng)的路徑權(quán)值（更新源點將新加入節(jié)點作為中間節(jié)點到達其它節(jié)點的距離）；重復該操作直到遍歷所有頂點，此時S中的集合就是起點A到其他各個頂點的最短路徑。
迪杰斯特拉算法只支持非負權(quán)圖，它計算的是單源最短路徑，即單個源點到剩余節(jié)點的最短路徑，時間復雜度為O(n²)，對稀疏圖運行更快。如果想知道所有頂點到所有頂點的最短路徑，那么等于在原有算法的基礎(chǔ)上，再來一次循環(huán)，此時整個算法的時間復雜度就成了O(n³)。
2.2 案例分析
該案例對應(yīng)著下面實現(xiàn)代碼中的案例，設(shè)起始點為A，初始化A到其他點的路徑數(shù)組{0, 99, 8, 2, 99, 3, 99}，初始化標志位數(shù)組{true, false, false, false, false, false, false}。
開始第一輪循環(huán)，排除已找到的路徑，即排除0，尋找到A的最短路徑，找到了A-D，即索引為3的頂點,設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的D可達的頂點路徑到A點的最短路徑，如果經(jīng)過D點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
這里D點可達C、B，D-C+A-D=7<8，因此更新A-C的最短路徑為7；D-B+A-D=11<99，因此更新A-B的最短路徑為11，第一輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 99, 3, 99}，標志位數(shù)組為{true, false, false, true, false, false, false}:
開始第二輪循環(huán)，排除已找到的路徑，即排除0、2，尋找到A的最短路徑，這里找到3，即索引為5的頂點，即A-F，設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的F可達的頂點路徑到A點的最短路徑，如果經(jīng)過F點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
這里F點可達G，F(xiàn)-G+A-F=12<99，因此更新A-G的最短路徑為12，第二輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 99, 3, 12}，標志位數(shù)組為{true, false, false, true, false, true, false}。
開始第三輪循環(huán)，排除已找到的路徑，即排除0、2、3，尋找到A的最短路徑，這里找到7，即索引為2的頂點，即A-C，設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的C可達的頂點路徑到A點的最短路徑，如果經(jīng)過C點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
這里C點可達B，C-B+A-C=11 = 11，因此不更新A-B的最短路徑，第三輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 99, 3, 12}，標志位數(shù)組為{true, false, true, true, false, true, false}。
開始第四輪循環(huán)，排除已找到的路徑，即排除0、2、3、7，尋找到A的最短路徑，這里找到11，即索引為1的頂點，即A-B，設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的B可達的頂點路徑到A點的最短路徑，如果經(jīng)過B點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
這里B點可達E，B-E+A-B=18 < 99，因此更新A-E的最短路徑為18，第四輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 18, 3, 12}，標志位數(shù)組為{true, true, true, true, false, true, false}。
開始第五輪循環(huán)，排除已找到的路徑，即排除0、2、3、7、11，尋找到A的最短路徑，這里找到12，即索引為6的頂點，即A-G，設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的G可達的頂點路徑到A點的最短路徑，如果經(jīng)過G點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
排除已找到的頂點，這里G點可達E，G-E+A-G=18 = 18，因此不更新最短路徑，第五輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 18, 3, 12}，標志位數(shù)組為{true, true, true, true, false, true, true}。
開始第六輪循環(huán)，排除已找到的路徑，即排除0、2、3、7、11、12，尋找到A的最短路徑，這里找到18，即索引為4的頂點，即A-E，設(shè)置對應(yīng)位置的最短路徑標志位為true，更新未獲取最短路徑的頂點的最短路徑，因為其他已找到的頂點的最短路徑已經(jīng)找到了，這里只需要更新新找到的E可達的頂點路徑到A點的最短路徑，如果經(jīng)過E點的路徑比數(shù)組中已存在的最短路徑小，那么更新值。
排除已找到的頂點，這里不更新最短路徑，第四輪循環(huán)結(jié)束，此時最短路徑數(shù)組為{0, 11, 7, 2, 18, 3, 12}，標志位數(shù)組為{true, true, true, true, true, true, true}。
此時大循環(huán)結(jié)束，Dijkstra算法結(jié)束，頂點A到各個頂點的最短路徑已經(jīng)找到，即A到{A,B,C,D,E,F,G}的最短路徑為{0, 11, 7, 2, 18, 3, 12}。
3 弗洛伊德（Floyd）算法
3.1 原理
弗洛伊德（Floyd）算法又稱插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法。算出來的結(jié)果是所有的節(jié)點到其余各節(jié)點之間的最短距離。
通用步驟如下：
1.設(shè)圖頂點數(shù)為N。首先需要準備一個長度為N的距離矩陣S，矩陣S中的元素a[i][j]=sum的表示頂點i到頂點j的最短路徑為sum；
2.然后對S矩陣進行初始化，距離矩陣S中頂點a[i][j]的值為頂點i到頂點j的直接權(quán)值；
3.然后對S矩陣循環(huán)進行N次更新，在第k次更新時，如果S矩陣的a[i][j] > a[i][k]+a[k][j]，那么更新a[i][j]=a[i][k]+a[k][j]。循環(huán)更新完畢，則算法完成，所有的節(jié)點到其余各節(jié)點之間的最短距離已經(jīng)找到了。
相比于Dijkstra 算法，F(xiàn)loyd算法支持帶有負權(quán)邊的圖，但是不能解決帶有“負權(quán)回路”（或者叫“負權(quán)環(huán)”）的圖，實際上如果一個圖中帶有“負權(quán)回路”那么這個圖則沒有最短路徑。
Floyd算法的時間復雜度同樣是時間復雜度O(n³)，空間復雜度是O(n²)，代碼非常簡單，但是思想相卻是非常的巧妙，將所有的可能都枚舉出來一一對比，取最小值，這樣最終會得到最小值。
3.2 案例分析
該案例對應(yīng)著下面實現(xiàn)代碼中的案例：
首先初始化距離矩陣S如下：
然后就是三層嵌套循環(huán)，開始第一輪大循環(huán)，即當k=0，循環(huán)遍歷S矩陣，判斷是否小于 shortestPath[i][j]，即所有的路徑都經(jīng)過A點中轉(zhuǎn)，如果經(jīng)過A中轉(zhuǎn)后的路徑shortestPath[i][0] + shortestPath[k][0]< shortestPath[i][j]，自然更新路徑：shortestPath[i][j]= shortestPath[i][0] + shortestPath[k][0]。一輪大循環(huán)之后的數(shù)組如下：
然后經(jīng)過一共經(jīng)過N次的大循環(huán)，表示經(jīng)過所有的頂點，最終取得的矩陣如下：
4 鄰接矩陣加權(quán)圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接矩陣實現(xiàn)無向加權(quán)圖的類，并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法，提供Dijkstra和Floyd兩種求最短路徑的方法。
/**
* 無向加權(quán)圖鄰接矩陣實現(xiàn)
* {@link MatrixDijkstraAndFloyd#MatrixDijkstraAndFloyd(Object[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link MatrixDijkstraAndFloyd#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixDijkstraAndFloyd#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixDijkstraAndFloyd#toString()} 輸出無向加權(quán)圖
* {@link MatrixDijkstraAndFloyd#prim()} Prim算法實現(xiàn)最小生成樹
* {@link MatrixDijkstraAndFloyd#kruskal()} Kruskal算法實現(xiàn)最小生成樹
* {@link MatrixDijkstraAndFloyd#kruskalAndPrim()} Kruskal算法結(jié)合Prim算法實現(xiàn)最小生成樹
* {@link MatrixDijkstraAndFloyd#getEdges()} 獲取邊集數(shù)組
* {@link MatrixDijkstraAndFloyd#dijkstra(int)} ()} Dijkstra算法獲取指定頂點到所有頂點的最短路徑
* {@link MatrixDijkstraAndFloyd#dijkstra(int, int)} Dijkstra算法獲取指定頂點到指定頂點的最短路徑
* {@link MatrixDijkstraAndFloyd#floyd()} Floyd獲取所有頂點到所有頂點的最短路徑
*
* @author lx
*/
public class MatrixDijkstraAndFloyd<E> {
/**
* 頂點數(shù)組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/**
*
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實際應(yīng)用中，該值應(yīng)該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 邊對象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vertexs 頂點數(shù)組
* @param edges 邊對象數(shù)組
*/
public MatrixDijkstraAndFloyd(Object[] vertexs, Edge<E>[] edges) {
//初始化邊數(shù)組
this.edges = edges;
// 初始化頂點數(shù)組,并添加頂點
this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
// 初始化邊矩陣,并預先填充邊信息
this.matrix = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = NO_EDGE;
}
}
}
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點和結(jié)束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
//對稱的兩個點位都置為edge.weight,無向圖可以看作相互可達的有向圖
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight;
}
}
/**
* 獲取某條邊的某個頂點所在頂點數(shù)組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點的所有鄰接點。若該鄰接點是沒有訪問過，那么繼續(xù)遞歸遍歷領(lǐng)接點
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出隊列
Integer j = indexLinkedList.poll();
//繼續(xù)訪問j的鄰接點
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續(xù)入隊列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
/**
* 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點v在數(shù)組中的索引
* @return 返回頂點v的第一個鄰接頂點的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 從i=0開始*/
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 返回頂點v相對于w的下一個鄰接頂點的索引，失敗則返回-1
*
* @param v 頂點索引
* @param w 第一個鄰接點索引
* @return 返回頂點v相對于w的下一個鄰接頂點的索引，失敗則返回-1
*/
private int nextVertex(int v, int w) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點索引v對應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 由于鄰接點w的索引已經(jīng)獲取了,所以從i=w+1開始尋找*/
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 輸出圖
*
* @return 輸出圖字符串
*/
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append("\t");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對應(yīng)節(jié)點應(yīng)該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[matrix.length];
//如果某頂點作為末端頂點被連接，對應(yīng)位置應(yīng)該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
//存儲未連接頂點到已連接頂點的最短距離(最小權(quán))
int[] dis = new int[matrix.length];
//首先將矩陣第一行即其他頂點到0索引頂點的權(quán)值拷貝進去
System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
//存儲路徑長度
int sum = 0;
//最小權(quán)值
int min;
/*默認第一個頂點已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點的索引
int minIndex = 0;
/*尋找權(quán)值最小的且未被連接的頂點索引*/
for (int i = 1; i < matrix.length; i++) {
//排除已連接的頂點,排除權(quán)值等于0的值,這里權(quán)值等于0表示已生成的最小生成樹的頂點都未能與該頂點連接
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點對應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應(yīng)的前驅(qū)頂點到該最小頂點的權(quán)值
System.out.println("\t" + vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權(quán)值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權(quán)值已經(jīng)計算過了
因此只需要更新其他未連接頂點到新連接頂點minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點權(quán)最小的頂點*/
for (int i = 1; i < matrix.length; i++) {
//如果該頂點未連接
if (!connected[i]) {
/*如果新頂點到未連接頂點i的權(quán)值不為0,并且比原始頂點到未連接頂點i的權(quán)值還要小,那么更新對應(yīng)位置的最小權(quán)值*/
if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
//更新最小權(quán)值
dis[i] = matrix[minIndex][i];
//更新前驅(qū)節(jié)點索引為新加入節(jié)點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
/**
* Kruskal算法求最小生成樹傳統(tǒng)實現(xiàn),要求知道邊集數(shù)組,和頂點數(shù)組
*/
public void kruskal() {
System.out.println("Kruskal: ");
//由于創(chuàng)建圖的時候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數(shù)組進行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
int[] vends = new int[this.edges.length];
//能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點索引to
int to = getPosition(edge.to);
// 獲取頂點from在"已有的最小生成樹"中的終點
int m = getEndIndex(vends, from);
// 獲取頂點to在"已有的最小生成樹"中的終點
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println("\t" + vertexs[from] + " ---> " + vertexs[to] + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("\t" + "sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
*
* @param vends 頂點在最小生成樹中的終點
* @param i 頂點索引
* @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接矩陣結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
/*遍歷矩陣數(shù)組 只需要遍歷一半就行了*/
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
//如果存在邊
if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) {
edges.add(new Edge<>(vertexs[i], vertexs[j], matrix[i][j]));
//edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges.toArray(new Edge[0]);
}
/**
* Kruskal結(jié)合Prim算法.不需要知道邊集,只需要矩陣數(shù)組,和頂點數(shù)組
* 同樣是求最小權(quán)值的邊,但是有一個默認起點頂點,該起點可以是要求[0,頂點數(shù)量-1]之間的任意值，同時查找最小權(quán)的邊。
* 可能會有Bug,目前未發(fā)現(xiàn)
*/
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已經(jīng)找到的邊攜帶的頂點對應(yīng)的索引將變?yōu)閠rue,其余未找到邊對應(yīng)的頂點將是false
boolean[] connected = new boolean[matrix.length];
//這里選擇第一個頂點為起點,表示以該頂點開始尋找包含該頂點的最小邊
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
//最小權(quán)值
int min;
while (true) {
min = NO_EDGE;
/*找出所有帶有已找到頂點的邊中,最小權(quán)值的邊,只需要尋找對稱矩陣的一半即可*/
//第一維
for (int i = 0; i < matrix.length; i++) {
//第二維
for (int j = i + 1; j < matrix.length; j++) {
//排除等于0的,排除兩個頂點都找到了的,這里實際上已經(jīng)隱含了排除環(huán)的邏輯,如果某條邊的兩個頂點都找到了,那么如果算上該條邊,肯定會形成環(huán)
//尋找剩下的最小的權(quán)值的邊
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果沒找到最小權(quán)值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
if (min == NO_EDGE) {
System.out.println("\t" + "sum:" + sum);
return;
}
//已經(jīng)找到的邊對應(yīng)的兩個頂點都置為true
connected[n1] = true;
connected[n2] = true;
//輸出找到的邊和最小權(quán)值
System.out.println("\t" + vertexs[n1] + " ---> " + vertexs[n2] + " 權(quán)值:" + min);
sum += min;
}
}
/**
* Dijkstra算法求最短路徑。
*
* @param start 起始頂點索引。即計算"頂點vs"到其它頂點的最短路徑。
*/
public void dijkstra(int start) {
checkIndex(start);
int[] shortestPathance = getShortestDistance(start, vertexs.length);
// 打印Dijkstra最短路徑的結(jié)果
System.out.println("Dijkstra(" + vertexs[start] + "):");
for (int i = 0; i < vertexs.length; i++) {
System.out.println("\t(" + vertexs[start] + " ---> " + vertexs[i] + ")最短路徑:" + shortestPathance[i]);
}
}
/**
* Dijkstra算法求最短路徑
*
* @param start 起始點
* @param end 終點,如果end=vertexs.length說明是遍歷查找所有的最短路徑
* @return 起始頂點到其他點或者指定點的最短權(quán)值
*/
private int[] getShortestDistance(int start, int end) {
/*1、該數(shù)組存放起始頂點到其他點的權(quán)值*/
int[] shortestPathance = new int[vertexs.length];
//初始化數(shù)據(jù)
//首先設(shè)置起始點到頂點i到的最短路徑為起始點到頂點i的權(quán)。
System.arraycopy(matrix[start], 0, shortestPathance, 0, matrix.length);
/*2、標志位數(shù)組.某個位置如果為true表示對應(yīng)位置的頂點到起始頂點的最短路徑已成功獲取。*/
boolean[] shortest = new boolean[vertexs.length];
//首先設(shè)置起始點到自己的的路徑已經(jīng)找到了,為0
shortest[start] = true;
/*3、最多遍歷vertexs.length-1次；每次找出起始點到一個頂點的最短路徑。*/
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// 尋找當前最小的路徑；
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
//排除已經(jīng)找到的最短路徑之后，找到離start最近的頂點(k)。
if (!shortest[j] && shortestPathance[j] < min) {
min = shortestPathance[j];
k = j;
}
}
//先設(shè)置起始點到新頂點k的最短路徑已經(jīng)找到
shortest[k] = true;
if (end != vertexs.length && k == end) {
break;
}
//更新未獲取最短路徑的頂點的最短路徑,因為其他已找到的頂點的最短路徑已經(jīng)找到了,這里指需要更新新加入的已找到的可達頂點的路徑.
for (int j = 0; j < vertexs.length; j++) {
int tmp = matrix[k][j];
//排除已經(jīng)找到的最短路徑，排除未連接的路徑，排除等于0的路徑（連接自己）之后
//找到離start最如果新的最短路徑比以前的最短路徑還要短，則更新最短路徑。
if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < shortestPathance[j])) {
shortestPathance[j] = tmp;
}
}
}
return shortestPathance;
}
/**
* 索引檢查
*
* @param index 多個索引
*/
private void checkIndex(int... index) {
for (int i : index) {
if (i < 0 || i >= vertexs.length) {
throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
}
}
}
/**
* Dijkstra算法求最短路徑。
*
* @param start 起始頂點索引。
* @param end 結(jié)束點索引
*/
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// 打印Dijkstra最短路徑的結(jié)果
System.out.println("Dijkstra(" + vertexs[start] + " ---> " + vertexs[end] + ")最短路徑:" + shortestPathance[end]);
}
/**
* Floyd算法獲取所有頂點到所有頂點的最短路徑,代碼很簡單,思想很巧妙
*/
public void floyd() {
//路徑矩陣(兩頂點最短路徑,即最小權(quán)值)
int[][] shortestPath = new int[matrix.length][matrix.length];
/*初始化數(shù)據(jù)*/
for (int i = 0; i < matrix.length; i++) {
System.arraycopy(matrix[i], 0, shortestPath[i], 0, vertexs.length);
}
// 計算最短路徑
for (int k = 0; k < matrix.length; k++) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
//要求經(jīng)過下標k頂點的兩個路徑都不能等于NO_EDGE,否則就是沒有路徑,NO_EDGE應(yīng)該選取的足夠的大,否則可能出錯
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
// 如果經(jīng)過下標為k頂點路徑比原兩點間路徑更短，則更新shortestPath[i][j]
if (shortestPath[i][j] > tmp) {
// i到j(luò)最短路徑對應(yīng)的值設(shè)為經(jīng)過k的更小的一個
shortestPath[i][j] = tmp;
}
}
}
}
/*輸出路徑矩陣*/
System.out.println("Floyd: ");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
System.out.print("\t" + shortestPath[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//頂點數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge<>('A', 'C', 8),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 9),
new Edge<>('F', 'G', 9)};
//構(gòu)建圖
MatrixDijkstraAndFloyd<Character> matrixDijkstraAndFloyd = new MatrixDijkstraAndFloyd<Character>(vexs, edges);
//輸出圖
System.out.println(matrixDijkstraAndFloyd);
//深度優(yōu)先遍歷
matrixDijkstraAndFloyd.DFS();
//廣度優(yōu)先遍歷
matrixDijkstraAndFloyd.BFS();
//Prim算法輸出最小生成樹
matrixDijkstraAndFloyd.prim();
//Kruskal算法輸出最小生成樹
matrixDijkstraAndFloyd.kruskal();
//Kruskal算法結(jié)合Prim算法輸出最小生成樹,可能會有Bug,目前未發(fā)現(xiàn)
matrixDijkstraAndFloyd.kruskalAndPrim();
// Dijkstra算法獲取某個索引的頂點到其它各個頂點的最短距離
// 這里參數(shù)是索引,也可以是一個頂點,需要稍微修改代碼獲取頂點的索引,比較簡單這里就不做了
matrixDijkstraAndFloyd.dijkstra(0);
// Dijkstra算法獲取一個頂點到另一個頂點的最短距離
matrixDijkstraAndFloyd.dijkstra(2, 0);
// Floyd算法獲取所有頂點到所有頂點的最短路徑
matrixDijkstraAndFloyd.floyd();
}
}
5 鄰接表加權(quán)圖實現(xiàn)
這里的實現(xiàn)能夠構(gòu)造一個基于鄰接表實現(xiàn)無向加權(quán)圖的類；并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法，提供Dijkstra和Floyd兩種求最短路徑的方法。
/**
* 無向加權(quán)圖鄰接表實現(xiàn)
* {@link ListDijkstraAndFloyd#ListDijkstraAndFloyd(Object[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link ListDijkstraAndFloyd#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link ListDijkstraAndFloyd#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link ListDijkstraAndFloyd#toString()} 輸出無向加權(quán)圖
* {@link ListDijkstraAndFloyd#prim()} Prim算法實現(xiàn)最小生成樹
* {@link ListDijkstraAndFloyd#kruskal()} Kruskal算法實現(xiàn)最小生成樹
* {@link ListDijkstraAndFloyd#getEdges()} 獲取邊集數(shù)組
* {@link ListDijkstraAndFloyd#dijkstra(int)} ()} 獲取指定頂點到所有頂點的最短路徑
* {@link ListDijkstraAndFloyd#dijkstra(int, int)} 獲取指定頂點到指定頂點的最短路徑
* {@link ListDijkstraAndFloyd#floyd()} Floyd獲取所有頂點到所有頂點的最短路徑
*
* @author lx
*/
public class ListDijkstraAndFloyd<E> {
/**
* 頂點類
*
* @param <E>
*/
private class Node<E> {
/**
* 頂點信息
*/
E data;
/**
* 指向第一條依附該頂點的邊
*/
LNode firstLNode;
public Node(E data, LNode firstLNode) {
this.data = data;
this.firstLNode = firstLNode;
}
}
/**
* 邊表節(jié)點類
*/
private class LNode {
/**
* 該邊所指向的頂點的索引位置
*/
int vertex;
/**
* 該邊的權(quán)值
*/
int weight;
/**
* 指向下一條邊的指針
*/
LNode nextLNode;
}
/**
* 邊對象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 頂點數(shù)組
*/
private Node<E>[] vertexs;
/**
* 邊數(shù)組
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實際應(yīng)用中，該值應(yīng)該根據(jù)實際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vexs 頂點數(shù)組
* @param edges 邊二維數(shù)組
*/
public ListDijkstraAndFloyd(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
/*初始化頂點數(shù)組,并添加頂點*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,并添加邊節(jié)點到邊表尾部,即采用尾插法*/
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點和結(jié)束頂點索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
/*這里需要相互添加邊節(jié)點,無向圖可以看作相互可達的有向圖*/
// 初始化lnode1邊節(jié)點
LNode lnode1 = new LNode();
lnode1.vertex = p2;
lnode1.weight = weight;
// 將LNode鏈接到"p1所在鏈表的末尾"
if (vertexs[p1].firstLNode == null) {
vertexs[p1].firstLNode = lnode1;
} else {
linkLast(vertexs[p1].firstLNode, lnode1);
}
// 初始化lnode2邊節(jié)點
LNode lnode2 = new LNode();
lnode2.vertex = p1;
lnode2.weight = weight;
// 將lnode2鏈接到"p2所在鏈表的末尾"
if (vertexs[p2].firstLNode == null) {
vertexs[p2].firstLNode = lnode2;
} else {
linkLast(vertexs[p2].firstLNode, lnode2);
}
}
}
/**
* 獲取某條邊的某個頂點所在頂點數(shù)組的索引位置
*
* @param e 頂點的值
* @return 所在頂點數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節(jié)點鏈接到邊表的最后,采用尾插法
*
* @param first 邊表頭結(jié)點
* @param node 將要添加的節(jié)點
*/
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextLNode == null) {
break;
}
first = first.nextLNode;
}
first.nextLNode = node;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstLNode;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");
node = node.nextLNode;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點索引
* @param visited 訪問標志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標記為true ,表示已經(jīng)訪問了
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點的邊表頭結(jié)點
LNode node = vertexs[i].firstLNode;
//循環(huán)遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
System.out.print("\t");
/*循環(huán)搜索*/
for (int i = 0; i < vertexs.length; i++) {
//如果對應(yīng)索引的頂點的訪問標記為false,則搜索該頂點
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點訪問標記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/
System.out.println();
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點訪問標記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
System.out.print("\t");
for (int i = 0; i < vertexs.length; i++) {
//如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判斷隊列是否有值,有就開始遍歷
if (!indexLinkedList.isEmpty()) {
//出隊列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstLNode;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//繼續(xù)入隊列
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對應(yīng)節(jié)點應(yīng)該被連接的前驅(qū)節(jié)點,用來輸出
//默認為0,即前驅(qū)結(jié)點為第一個節(jié)點
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//頂點間邊的權(quán)值
//存儲未連接頂點到已連接頂點的最短距離(最小權(quán))
int[] dis = new int[num];
// 初始化"頂點的權(quán)值數(shù)組"，
// 將每個頂點的權(quán)值初始化為"第start個頂點"到"該頂點"的權(quán)值。
//首先將其他頂點到0索引頂點的權(quán)值存儲進去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某頂點作為末端頂點被連接，對應(yīng)位置應(yīng)該為true
//第一個頂點默認被連接
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
/*默認第一個頂點已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < num; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點的索引
int minIndex = 0;
// 在未被加入到最小生成樹的頂點中，找出權(quán)值最小的頂點。
for (int i = 1; i < vertexs.length; i++) {
//排除已連接的頂點,排除權(quán)值等于0的值,因為這里默認頂點指向自己的權(quán)值為0
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點對應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時跳過該頂點
connected[minIndex] = true;
//輸出對應(yīng)的前驅(qū)頂點到該最小頂點的權(quán)值
System.out.println("\t" + vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權(quán)值:" + min);
/*在新頂點minIndex加入之前的其他所有頂點到連接頂點最小的權(quán)值已經(jīng)計算過了
因此只需要更新其他頂點到新連接頂點minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點權(quán)最小的頂點*/
for (int i = 1; i < num; i++) {
//如果該頂點未連接
if (!connected[i]) {
// 獲取minindex頂點到未連接頂點i的權(quán)值
tmp = getWeight(minIndex, i);
/*如果新頂點到未連接頂點i的權(quán)值不為0,并且比原始頂點到未連接頂點i的權(quán)值還要小,那么更新對應(yīng)位置的最小權(quán)值*/
if (tmp != 0 && dis[i] > tmp) {
dis[i] = tmp;
//更新前驅(qū)節(jié)點索引為新加入節(jié)點索引
mid[i] = minIndex;
}
}
}
}
System.out.println("\t" + "sum: " + sum);
}
/**
* 嘗試獲取邊起點start到邊終點end的邊的權(quán)值,當然可能獲取不到
*
* @param start 邊起點
* @param end 邊終點
* @return 返回權(quán)值; 如果起點和終點相同則返回0;如果邊起點和邊終點之間并沒有邊, 則返回NO_EDGE
*/
private int getWeight(int start, int end) {
//如果start=end，則返回0
if (start == end) {
return 0;
}
//獲取該頂點的邊表的第一個值
LNode node = vertexs[start].firstLNode;
//循環(huán)查找邊表,看能否找到對應(yīng)的索引=end,找不到就返回NO_EDGE,表示兩個頂點未連接。
while (node != null) {
if (end == node.vertex) {
return node.weight;
}
node = node.nextLNode;
}
return NO_EDGE;
}
/**
* Kruskal算法求最小生成樹,可以說鄰接矩陣和鄰接鏈表的實現(xiàn)方式是完全一致的
*/
public void kruskal() {
System.out.println("Kruskal: ");
//由于創(chuàng)建圖的時候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對邊集數(shù)組進行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個頂點在該最小樹中的最終終點的索引
int[] vends = new int[this.edges.length];
//能夠知道終點索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點索引to
int to = getPosition(edge.to);
// 獲取頂點from在"已有的最小生成樹"中的終點
int m = getEndIndex(vends, from);
// 獲取頂點to在"已有的最小生成樹"中的終點
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點索引m在已有的最小生成樹中的終點為n
vends[m] = n;
System.out.println("\t" + vertexs[from].data + " ---> " + vertexs[to].data + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("\t" + "sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點索引i的終點如果沒有終點則返回頂點索引本身
*
* @param vends 頂點在最小生成樹中的終點
* @param i 頂點索引
* @return 頂點索引i的終點如果沒有終點則返回頂點索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接表結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
//遍歷頂點數(shù)組
for (int i = 0; i < vertexs.length; i++) {
LNode node = vertexs[i].firstLNode;
while (node != null) {
//只需添加起點索引小于終點索引的邊就行了
if (node.vertex > i) {
edges.add(new Edge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight));
}
node = node.nextLNode;
}
}
return edges.toArray(new Edge[0]);
}
/**
* Dijkstra算法求最短路徑。
*
* @param start 起始頂點索引。即計算"頂點vs"到其它頂點的最短路徑。
*/
public void dijkstra(int start) {
checkIndex(start);
int[] distance = getShortestDistance(start, vertexs.length);
// 打印dijkstra最短路徑的結(jié)果
System.out.println("dijkstra(" + vertexs[start].data + "):");
for (int i = 0; i < vertexs.length; i++) {
System.out.println("\t(" + vertexs[start].data + " ---> " + vertexs[i].data + ")最短路徑:" + distance[i]);
}
}
/**
* Dijkstra算法求最短路徑。
*
* @param start 起始頂點索引。
* @param end 結(jié)束點索引
*/
public void dijkstra(int start, int end) {
checkIndex(start, end);
int[] shortestPathance = getShortestDistance(start, end);
// 打印dijkstra最短路徑的結(jié)果
System.out.println("Dijkstra(" + vertexs[start].data + " ---> " + vertexs[end].data + ")最短路徑:" + shortestPathance[end]);
}
/**
* Dijkstra算法求最短路徑
*
* @param start 起始點
* @param end 終點,如果end=vertexs.length說明是遍歷查找所有的最短路徑
* @return 起始頂點到其他點或者指定點的最短權(quán)值
*/
private int[] getShortestDistance(int start, int end) {
/*1、該數(shù)組存放起始頂點到其他點的權(quán)值*/
int[] distance = new int[vertexs.length];
//初始化數(shù)據(jù)
for (int i = 0; i < vertexs.length; i++) {
//首先設(shè)置起始點到頂點i到的最短路徑為起始點到頂點i的權(quán)。
distance[i] = getWeight(start, i);
}
/*2、標志位數(shù)組.某個位置表示true表示,對應(yīng)位置的頂點到起始頂點的最短路徑已成功獲取。*/
boolean[] shortest = new boolean[vertexs.length];
//首先設(shè)置起始點到自己的的路徑已經(jīng)找到了,為0
shortest[start] = true;
/*3、最多遍歷vertexs.length-1次；每次找出起始點到一個頂點的最短路徑。*/
int k;
int min;
for (int i = 1; i < vertexs.length; i++) {
k = 0;
// 尋找當前最小的路徑；
min = NO_EDGE;
for (int j = 0; j < vertexs.length; j++) {
//排除已經(jīng)找到的最短路徑之后，找到離start最近的頂點(k)。
if (!shortest[j] && distance[j] < min) {
min = distance[j];
k = j;
}
}
//先設(shè)置起始點到新頂點k的最短路徑已經(jīng)找到
shortest[k] = true;
if (end != vertexs.length && k == end) {
break;
}
//更新未獲取最短路徑的頂點的最短路徑,因為其他已找到的頂點的最短路徑已經(jīng)找到了,這里指需要更新新加入的已找到的可達頂點的路徑.
for (int j = 0; j < vertexs.length; j++) {
int tmp = getWeight(k, j);
//排除已經(jīng)找到的最短路徑，排除未連接的路徑，排除等于0的路徑（連接自己）之后
//找到離start最如果新的最短路徑比以前的最短路徑還要短，則更新最短路徑。
if (!shortest[j] && tmp != NO_EDGE && tmp != 0 && ((tmp = min + tmp) < distance[j])) {
distance[j] = tmp;
}
}
}
return distance;
}
/**
* 索引檢查
*
* @param index 多個索引
*/
private void checkIndex(int... index) {
for (int i : index) {
if (i < 0 || i >= vertexs.length) {
throw new ArrayIndexOutOfBoundsException("索引越界:" + i);
}
}
}
/**
* Floyd算法獲取所有頂點到所有頂點的最短路徑,與鄰接矩陣的實現(xiàn)基本一致
*/
public void floyd() {
//路徑矩陣(兩頂點最短路徑,即最小權(quán)值)
int[][] shortestPath = new int[vertexs.length][vertexs.length];
/*初始化數(shù)據(jù)*/
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
//獲取兩點的直接權(quán)值
//如果是頻繁調(diào)用該方法,因此可以創(chuàng)建一個屬于對象的權(quán)值矩陣用來保存權(quán)值,這里為了簡單沒做
shortestPath[i][j] = getWeight(i, j);
}
}
// 計算最短路徑
for (int k = 0; k < vertexs.length; k++) {
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
//要求經(jīng)過下標k頂點的兩個路徑都不能等于NO_EDGE,否則就是沒有路徑,NO_EDGE應(yīng)該選取的足夠的大,否則可能出錯
int tmp = (shortestPath[i][k] == NO_EDGE || shortestPath[k][j] == NO_EDGE) ? NO_EDGE : (shortestPath[i][k] + shortestPath[k][j]);
// 如果經(jīng)過下標為k頂點路徑比原兩點間路徑更短，則更新shortestPath[i][j]
if (shortestPath[i][j] > tmp) {
// i到j(luò)最短路徑對應(yīng)的值設(shè)為經(jīng)過k的更小的一個
shortestPath[i][j] = tmp;
}
}
}
}
/*輸出路徑矩陣*/
System.out.println("Floyd: ");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.print("\t" + shortestPath[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//頂點數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge<>('A', 'C', 8),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 9),
new Edge<>('F', 'G', 9)};
//構(gòu)建圖
ListDijkstraAndFloyd<Character> listDijkstraAndFloyd = new ListDijkstraAndFloyd<Character>(vexs, edges);
//輸出圖
System.out.println(listDijkstraAndFloyd);
//深度優(yōu)先遍歷
//DFS:
//A C B E G F D
listDijkstraAndFloyd.DFS();
//廣度優(yōu)先遍歷
//BFS:
//A C D F B G E
listDijkstraAndFloyd.BFS();
//Prim算法求最小生成樹
listDijkstraAndFloyd.prim();
//Kruskal算法求最小生成樹
listDijkstraAndFloyd.kruskal();
// Dijkstra算法獲取某個索引的頂點到其它各個頂點的最短距離
// 這里參數(shù)是索引,也可以是一個頂點,需要稍微修改代碼獲取頂點的索引,比較簡單這里就不做了
listDijkstraAndFloyd.dijkstra(0);
// Dijkstra算法獲取一個頂點到另一個頂點的最短距離
listDijkstraAndFloyd.dijkstra(2, 0);
// Floyd算法獲取所有頂點到所有頂點的最短路徑
listDijkstraAndFloyd.floyd();
}
}
以上就是Java利用Dijkstra和Floyd分別求取圖的最短路徑的詳細內(nèi)容，更多關(guān)于Java求最短路徑的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了淺談Java并發(fā)編程基礎(chǔ)知識,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11
這篇文章主要介紹了Java編程調(diào)用微信支付功能的方法,結(jié)合實例形式詳細分析了java微信支付功能的原理、操作流程及相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2017-08-08
這篇文章主要為大家介紹了HttpClient中的close方法及其對連接的影響探索分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-10-10
SpringBoot中的異常處理與參數(shù)校驗的方法實現(xiàn)
這篇文章主要介紹了SpringBoot中的異常處理與參數(shù)校驗的方法實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-04-04
這篇文章主要介紹了java之函數(shù)式接口，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
今天帶大家學習Java基礎(chǔ)知識,文中對關(guān)鍵字final作了非常詳細的介紹,對正在學習Java的小伙伴們很有幫助,需要的朋友可以參考下2021-05-05
貪吃蛇是經(jīng)典手機游戲，既簡單又耐玩。通過控制蛇頭方向吃蛋，使得蛇變長，從而獲得積分。今天我們就來用java來實現(xiàn)下貪吃蛇小游戲，有需要的小伙伴可以參考下2015-03-03
Mybatis中${param}與#{param}的區(qū)別說明
這篇文章主要介紹了Mybatis中${param}與#{param}的區(qū)別說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
Java中private關(guān)鍵字詳細用法實例以及解釋
這篇文章主要給大家介紹了關(guān)于Java中private關(guān)鍵字詳細用法實例以及解釋的相關(guān)資料,在Java中private是一種訪問修飾符,它可以用來控制類成員的訪問權(quán)限,文中將用法介紹的非常詳細,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了Java SpringBoot攔截器的使用方法詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2021-10-10