本文以實例形式介紹了基于Java實現的Dijkstra算法，相信對于讀者研究學習數據結構域算法有一定的幫助。
Dijkstra提出按各頂點與源點v間的路徑長度的遞增次序，生成到各頂點的最短路徑的算法。即先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點v 到其它各頂點的最短路徑全部求出為止。
其代碼實現如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
package com.algorithm.impl;public class Dijkstra { private static int M = 10000; //此路不通 public static void main(String[] args) { int[][] weight1 = {//鄰接矩陣 {0,3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][] weight2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0,M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; int start=0; int[] shortPath = dijkstra(weight2,start); for(int i = 0;i < shortPath.length;i++) System.out.println("從"+start+"出發到"+i+"的最短距離為："+shortPath[i]); } public static int[] dijkstra(int[][] weight, int start) { //接受一個有向圖的權重矩陣，和一個起點編號start（從0編號，頂點存在數組中） //返回一個int[] 數組，表示從start到它的最短路徑長度 int n = weight.length; //頂點個數 int[] shortPath = new int[n]; //保存start到其他各點的最短路徑 String[] path = new String[n]; //保存start到其他各點最短路徑的字符串表示 for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visited = new int[n]; //標記當前該頂點的最短路徑是否已經求出,1表示已求出 //初始化，第一個頂點已經求出 shortPath[start] = 0; visited[start] = 1; for(int count = 1; count < n; count++) { //要加入n-1個頂點 int k = -1; //選出一個距離初始頂點start最近的未標記頂點 int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited[i] == 0 && weight[start][i] < dmin) { dmin = weight[start][i]; k = i; } } //將新選出的頂點標記為已求出最短路徑，且到start的最短路徑就是dmin shortPath[k] = dmin; visited[k] = 1; //以k為中間點，修正從start到未訪問各點的距離 for(int i = 0; i < n; i++) { if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) { weight[start][i] = weight[start][k] + weight[k][i]; path[i] = path[k] + "-->" + i; } } } for(int i = 0; i < n; i++) { System.out.println("從"+start+"出發到"+i+"的最短路徑為："+path[i]); } System.out.println("====================================="); return shortPath; }} |
該程序運行結果為：
|
1
2
3
4
5
6
7
8
9
10
11
|
從0出發到0的最短路徑為：0-->0從0出發到1的最短路徑為：0-->1從0出發到2的最短路徑為：0-->3-->2從0出發到3的最短路徑為：0-->3從0出發到4的最短路徑為：0-->3-->2-->4=====================================從0出發到0的最短距離為：0從0出發到1的最短距離為：10從0出發到2的最短距離為：50從0出發到3的最短距離為：30從0出發到4的最短距離為：60 |
