Java 實現 Dijsktra 算法

2019-11-06 07:45:01

字體：大中小

來源：轉載

供稿：網友

看看書中的描述：這里寫圖片描述

書中是用C++實現的，C++比較難，懂個思路就行，這里用java實現：

這里寫圖片描述

package graph;public class Dijkstra { PRivate static final int MAXSIZE = 1000; private static final int INF = 1200; private static final int N = 6; public static void main(String[] args) { System.out.println("------------Dijsktra------------"); int[][] data = { {MAXSIZE, 12, MAXSIZE, 12, 5, MAXSIZE}, {MAXSIZE, MAXSIZE, 7, MAXSIZE, 4, MAXSIZE}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, 1}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, 7}, {MAXSIZE, MAXSIZE, 14, 9, MAXSIZE, 32}, {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE}, }; int v = 1; System.out.println("打印有向圖的鄰接矩陣："); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { System.out.print(" " + data[i][j]); } System.out.println(); } System.out.println("打印原點1到其它各點的最短路徑及其長度："); toDijsktra(data, v); } private static void toDijsktra(int[][] data, int v) { //dist[]頂點到頂點的最短距離 int[] dist = new int[N]; //path[]存放上一個頂點 int[] path = new int[N]; //s[]存放已經加入到最短路徑的頂點 int[] s = new int[N]; int f = v - 1; //初始化第一個頂點 for(int i = 0; i < N; i++) { dist[i] = data[f][i]; if(dist[i] != MAXSIZE) { path[i] = v; } else { path[i] = 0; } } for(int i = 0; i < N; i++) { s[i] = 0; } //將第一個頂點加入最短路徑集合 s[f] = 1; //第一個頂點到第一個頂點的距離為0 dist[f] = 0; int k = 0; for(int i = 0; i < N - 1; i++) { int min = INF; //該for循環找出最短的邊 for(int j = 0; j < N; j++) { if((s[j] == 0) && (dist[j] < min)) { min = dist[j]; //最短邊的頂點賦給K k = j; } } //將K頂點加入最短路徑集合 s[k] = 1; //更新d[]的值，保證d[j]里面的值是有第一個頂點到k頂點的最短距離 for(int j = 0; j < N; j++) { if((s[j] == 0) && (dist[j] > (dist[k] + data[k][j]))) { dist[j] = dist[k] + data[k][j]; path[j] = k + 1; } } } for(int i = 0; i < N; i++) { System.out.print(v + "到" + (i+1) + "的最短距離是"); System.out.print(dist[i]); System.out.println(); int pre = path[i]; System.out.print("路徑:" + (i+1)); while(pre != 0) { System.out.print("<------" + pre); pre = path[pre-1]; } System.out.println(); System.out.println("-----------------------"); } }}

運行結果：

這里寫圖片描述