JAVA資料結構----------Dijstra（迪傑斯特拉）圖最短路徑算法

算法簡介

迪傑斯特拉(Dijkstra)算法是典型最短路徑算法，用于計算一個節點到其他節點的最短路徑。

它的主要特點是以起始點為中心向外層層擴充(廣度優先搜尋思想)，直到擴充到終點為止，是貪心算法的一種，但由于dijkstra算法主要計算從源點到其他所有點的最短路徑，是以算法的效率較低。

算法思路步驟

下述代碼是根據c語言改編過來的，大體思路如下

1.開始建構shortTablePath[]數組，目的是将已經知道最小的路徑放入，比如shortTablePath[4] = 9，意思就是v0到v4的最短路徑為9；布爾數組isgetPath[]表示該頂點是否已經找到最短路徑，比如isgetPath[4] = true 表示v0到v4已經找到最小路徑。

2.将鄰接矩陣的第一行指派給shortTablePath[]（将起點那行指派給shortTablePath[]），找到數組中的最小值，例子中應該找到v1，然後把sgetPath[1] = true表示v0到v1已經找到最短路徑了

3.然後找v1可以連接配接到的點且沒找到最短路徑的點即isgetPath = flase(v1可以連接配接到，v0也就可以間接連接配接到，間接連接配接到的點也有可能最短),比如v0——v1——v5路徑為4，v0——v5路徑為5，此時就将shortTablePath[5] = 4。注意的是鄰接矩陣我們将兩個沒有聯系的點權值設為1000（我想表示的是無窮大）比如最開始的時候shortTablePath[3] = 1000，即v0 ->v3權值為1000（表示無窮大）。v0->v1->v3 路徑為1+7 =8 ,故shortTablePath[3] 暫時為8，

4再次找shortTablePath數組中沒有找打最短路徑的點中的最小值(isgetPath = flase),進行第三步操作（其實也就是2,3步驟循環，直到isgetPath 中全部為true）

算法執行個體

要求：求出v0點到v8（終點)的最短路徑

import Graph;

/**
 * 迪傑斯特拉算法找連通圖的最小權值
 * @author 65481
 *
 */
public class DnjavaDijstra {
	//頂點個數
	private final static int MAXVEX = 9;
	//最大權值
	private final static int MAXWEIGHT = 1000;
	//存放已經找到的最小權值
	private int shortTablePath[] = new int[MAXVEX];
	
	/**
	 * 擷取一個圖的最短路徑
	 */
	public void shortesPathDijstra(Graph graph) {
		int min = 0 ;
		int  k = 0; //記錄下标
		
		//頂點是否已經拿到最短路徑
		boolean isgetPath[] = new boolean[MAXVEX];
		
		//初始化shortTablePath數組 使用臨接矩陣的第一行
		for(int i = 0 ;i < graph.getVertexSize();i ++) {
			shortTablePath[i] = graph.getMatrix()[0][i];
		}
		
		//預設從第0點出發 起始點到起始點的最短權值為0
		shortTablePath[0] = 0;
		//起始點已經被通路過了
		isgetPath[0] = true;
		
		//一共需要循環頂點數量減1 次
		for(int i = 1;i < graph.getVertexSize();i ++) {
			//找最小值
			min = MAXWEIGHT;
			for(int j = 0 ;j < graph.getVertexSize();j ++) {
				if (shortTablePath[j] < min && !isgetPath[j]) {
					min = shortTablePath[j];
					//記錄下标
					k = j;
				}
			}
			//k點已經找到了最小的權值
			isgetPath[k] = true;
			
			//更新shorttablepath
			for(int j = 0;j< graph.getVertexSize();j ++) {
				if(!isgetPath[j]&&(min + graph.getMatrix()[k][j] < shortTablePath[j])) {
					shortTablePath[j] = min + graph.getMatrix()[k][j];
				}
			}
		}
		for(int i = 0;i < graph.getVertexSize();i++) {
			System.out.println("v0到v"+i+"的最短路徑為"+shortTablePath[i]);
		}
	}
	
	
	
	public static void main(String[] args) {
		DnjavaDijstra dnjavaDijstra = new DnjavaDijstra();
		Graph graph = new Graph(MAXVEX);
		
		int [] a1 = {0,1,5,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a2 = {1,0,3,7,5,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a3 = {5,3,0,MAXWEIGHT,1,7,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT};
		int [] a4 = {MAXWEIGHT,7,MAXWEIGHT,0,2,MAXWEIGHT,3,MAXWEIGHT,MAXWEIGHT};
		int [] a5 = {MAXWEIGHT,5,1,2,0,3,6,9,MAXWEIGHT};
		int [] a6 = {MAXWEIGHT,MAXWEIGHT,7,MAXWEIGHT,3,0,MAXWEIGHT,5,MAXWEIGHT};
		int [] a7 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,3,6,MAXWEIGHT,0,2,7};
		int [] a8 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,9,5,2,0,4};
		int [] a9 = {MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,MAXWEIGHT,7,4,0};
		
		graph.getMatrix()[0] = a1;
		graph.getMatrix()[1] = a2;
		graph.getMatrix()[2] = a3;
		graph.getMatrix()[3] = a4;
		graph.getMatrix()[4] = a5;
		graph.getMatrix()[5] = a6;
		graph.getMatrix()[6] = a7;
		graph.getMatrix()[7] = a8;
		graph.getMatrix()[8] = a9;
		
		dnjavaDijstra.shortesPathDijstra(graph);
	}
}
           

在上述代碼中使用到了鄰接矩陣表示的圖，代碼如下

public class Graph {
	
	//聲明就是随便提一下 沒定義
	private int vertexSize; //頂點數量
	private int[] vertexs;//頂點數組
	private int[][] matrix;//鄰接矩陣
	private final static int MAX_WIGHT = 1000; //設定沒有關系的值
	
	
	public int[][] getMatrix() {
		return matrix;
	}

	public void setMatrix(int[][] matrix) {
		this.matrix = matrix;
	}

	public static int getMaxWight() {
		return MAX_WIGHT;
	}

	public void setVertexs(int[] vertexs) {
		this.vertexs = vertexs;
	}

	public int getVertexSize() {
		return vertexSize;
	}

	public void setVertexSize(int vertexSize) {
		this.vertexSize = vertexSize;
	}

	public Graph(int vertexSize) {
	this.vertexSize = vertexSize;
	//鄰接矩陣
	matrix =  new int[vertexSize][vertexSize];
	//頂點數組
	vertexs = new int[vertexSize];
	for(int i = 0;i <vertexSize;i++) {
		vertexs[i] = i; 
	}
	}

	public int[] getVertexs() {
		return vertexs;
	}


	public void setVertex(int[] vertexs) {
		this.vertexs = vertexs;
	}
}
           

運作結果如下:

v0到v0的最短路徑為0

v0到v1的最短路徑為1

v0到v2的最短路徑為4

v0到v3的最短路徑為7

v0到v4的最短路徑為5

v0到v5的最短路徑為8

v0到v6的最短路徑為10

v0到v7的最短路徑為12

v0到v8的最短路徑為16