現有場景:最短路徑問題
戰争時期,勝利鄉有7個村莊(A,B,C,D,E,F,G),現在有六個油差,從G點出發,需要分别把郵件分别送到A,B,C,D,E,F,G六個村莊,各個村莊的路基用邊線表示權,比如A–B距離5公裡,問:如何計算出G村莊到其他各個村莊的最短距離?
1.迪傑斯特拉算法
迪傑斯特拉(Dijkstra)算法是典型最短路徑算法,用于計算一個節點到其他節點的最短路徑,它的主要特點是以起始點為中心向外層擴充(廣度優先思想),直到擴充到終點為止.
迪傑斯特拉算法過程:
設定出發點為v,頂點集合V{v1,v2,v3,…},v到V中個頂點的距離構成距離集合Dis,Dis{d1,d2,d3…},Dis集合記錄看v到圖中各頂點的距離(到自身可以看作0,v到vi距離對應為di)
(1)從Dis中選擇值最小的di并移出Dis集合,同時移出V集合中對應的頂點vi,此時的v到vi即為最短路徑
(2)更新Dis集合,更新規則為:比較v到V集合中頂點的距離值,與v通過vi到V集合中頂點的距離值,保留值較小的一個(同時也應該更新頂點的前驅節點為vi,表明是通過vi達到的)
(3)重複執行以上兩步驟,知道最短路徑頂點為目标頂點即可結束
接下來部落客準備了張圖檔,友善了解
代碼實作:
package com.self.tenAlgorithm;
import java.util.Arrays;
public class DijkstraAlgorithm {
private static final int N = 65535;
public static void main(String[] args) {
char[] vertex = {'A','B','C','D','E','F','G'};
int[][] matrix = new int[vertex.length][vertex.length];
matrix[0] = new int[]{N,5,7,N,N,N,2};
matrix[1] = new int[]{5,N,N,9,N,N,3};
matrix[2] = new int[]{7,N,N,N,8,N,N};
matrix[3] = new int[]{N,9,N,N,N,4,N};
matrix[4] = new int[]{N,N,8,N,N,5,4};
matrix[5] = new int[]{N,N,N,4,5,N,6};
matrix[6] = new int[]{2,3,N,N,4,6,N};
Graph graph = new Graph(vertex, matrix);
graph.showGraph();
graph.djs(2);
graph.showDJS();
}
}
class Graph{
private char[] vertex; //頂點數組
private int[][] matrix; //鄰接矩陣
private VisitedVertex vv; //表示已經通路頂點集合
public Graph(char[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}
//顯示圖
public void showGraph(){
for (int[] link : matrix) {
System.out.println(Arrays.toString(link));
}
}
/**
* 功能:迪傑斯特拉算法實作
* @param index 表示出發頂點對應的下标
*/
public void djs(int index){
vv = new VisitedVertex(vertex.length, index);
update(index);
for (int i = 0; i < vertex.length; i++) {
index = vv.updateArr(); //選擇并傳回新的通路頂點
update(index);
}
}
/**
* 功能:更新index下标頂點到周圍頂點的距離和周圍頂點的前驅節點
* @param index
*/
private void update(int index){
int len = 0; //len含義:出發頂點到index頂點的距離+從index頂點到j頂點的距離的和
//根據周遊我們的鄰接矩陣的matrix[index]行
for (int i = 0; i < matrix[index].length; i++) {
len = vv.getDis(index) + matrix[index][i];
//如果i頂點沒有被通路過,并且len小于出發頂點到j頂點的距離,就需要更新
if(!vv.whetherVisited(i) && len < vv.getDis(i)){
vv.updatePre(i,index); //更新i頂點到前驅為index頂點
vv.updateDis(i,len); //更新出發頂點到j頂點的距離
}
}
}
/**
* 顯示最後結果
*/
public void showDJS(){
vv.show();
}
}
//已通路頂點集合
class VisitedVertex{
//記錄各個頂點是否通路過 1表示通路過 0表示未通路,會動态更新
public int[] already_arr;
//每個下标對應的值為前一個頂點下标,會動态更新
public int[] pre_visited;
//記錄出發頂點到其他所有頂點的距離,比如G為出發頂點,就會記錄G到其他頂點的距離,會動态更新,求的最短距離就會存放到dis
public int[] dis;
/** 構造方法
* @param length 表示頂點的個數
* @param index 出發頂點對應的下标,比如G頂點,下标就是6
*/
public VisitedVertex(int length,int index) {
this.already_arr = new int[length];
this.pre_visited = new int[length];
this.dis = new int[length];
//初始化數組
Arrays.fill(dis,65535);
this.already_arr[index] = 1;
this.dis[index] = 0; //設定出發頂點的通路距離為0
}
/**
* @功能:判斷index是否被通路過
* @param index
* @return 如果通路過 傳回true,否則就通路false
*/
public boolean whetherVisited(int index){
return already_arr[index] == 1;
}
/**
* 功能:更新出發頂點到index頂點的距離
* @param index
* @param len
*/
public void updateDis(int index,int len){
dis[index] = len;
}
/**
* 功能:更新pre這個頂點的前驅頂點為index頂點
* @param pre
* @param index
*/
public void updatePre(int pre,int index){
pre_visited[pre] = index;
}
/**
* 功能:傳回出發頂點到index頂點的距離
* @param index
* @return
*/
public int getDis(int index){
return dis[index];
}
/**功能:繼續選擇并傳回新的頂點,比如這裡的G完後,就是A點作為新的通路頂點(注意不是出發頂點)
* @return
*/
public int updateArr(){
int min = 65535,index = 0;
for (int i = 0; i < already_arr.length; i++) {
if(already_arr[i] == 0 && dis[i] < min){
min = dis[i];
index = i;
}
}
//更新index頂點被通路過
already_arr[index] = 1;
return index;
}
/**
* 功能:顯示最後的結果,将三個數組的情況輸出
*/
public void show(){
System.out.println("============");
for (int i : already_arr) {
System.out.print(i+" ");
}
System.out.println();
for (int i : pre_visited) {
System.out.print(i+" ");
}
System.out.println();
for (int i : dis) {
System.out.print(i+" ");
}
System.out.println();
//為了友善看最後的最短距離
char[] vertex = {'A','B','C','D','E','F','G'};
int count = 0;
for (int i : dis) {
if(i != 65535){
System.out.print(vertex[count] + "("+i+")");
}else{
System.out.println("N");
}
count++;
}
System.out.println();
}
}
關于代碼比較複雜,是以部落客在代碼裡面做了詳細的注釋
運作結果:
[65535, 5, 7, 65535, 65535, 65535, 2]
[5, 65535, 65535, 9, 65535, 65535, 3]
[7, 65535, 65535, 65535, 8, 65535, 65535]
[65535, 9, 65535, 65535, 65535, 4, 65535]
[65535, 65535, 8, 65535, 65535, 5, 4]
[65535, 65535, 65535, 4, 5, 65535, 6]
[2, 3, 65535, 65535, 4, 6, 65535]
============
1 1 1 1 1 1 1
2 0 0 5 2 4 0
7 12 0 17 8 13 9
A(7)B(12)C(0)D(17)E(8)F(13)G(9)
大家可以自行選取出發點進行測試,然後手動比較進行驗證,歡迎留言,歡迎技術交流