本文以實(shí)例形式介紹了基于Java實(shí)現(xiàn)的Dijkstra算法，相信對(duì)于讀者研究學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)域算法有一定的幫助。
Dijkstra提出按各頂點(diǎn)與源點(diǎn)v間的路徑長(zhǎng)度的遞增次序，生成到各頂點(diǎn)的最短路徑的算法。即先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從源點(diǎn)v 到其它各頂點(diǎn)的最短路徑全部求出為止。
其代碼實(shí)現(xiàn)如下所示：
|
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+"出發(fā)到"+i+"的最短距離為："+shortPath[i]); } public static int[] dijkstra(int[][] weight, int start) { //接受一個(gè)有向圖的權(quán)重矩陣，和一個(gè)起點(diǎn)編號(hào)start（從0編號(hào)，頂點(diǎn)存在數(shù)組中） //返回一個(gè)int[] 數(shù)組，表示從start到它的最短路徑長(zhǎng)度 int n = weight.length; //頂點(diǎn)個(gè)數(shù) int[] shortPath = new int[n]; //保存start到其他各點(diǎn)的最短路徑 String[] path = new String[n]; //保存start到其他各點(diǎn)最短路徑的字符串表示 for(int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] visited = new int[n]; //標(biāo)記當(dāng)前該頂點(diǎn)的最短路徑是否已經(jīng)求出,1表示已求出 //初始化，第一個(gè)頂點(diǎn)已經(jīng)求出 shortPath[start] = 0; visited[start] = 1; for(int count = 1; count < n; count++) { //要加入n-1個(gè)頂點(diǎn) int k = -1; //選出一個(gè)距離初始頂點(diǎn)start最近的未標(biāo)記頂點(diǎn) 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; } } //將新選出的頂點(diǎn)標(biāo)記為已求出最短路徑，且到start的最短路徑就是dmin shortPath[k] = dmin; visited[k] = 1; //以k為中間點(diǎn)，修正從start到未訪問(wèn)各點(diǎn)的距離 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+"出發(fā)到"+i+"的最短路徑為："+path[i]); } System.out.println("====================================="); return shortPath; }} |
該程序運(yùn)行結(jié)果為：
|
1
2
3
4
5
6
7
8
9
10
11
|
從0出發(fā)到0的最短路徑為：0-->0從0出發(fā)到1的最短路徑為：0-->1從0出發(fā)到2的最短路徑為：0-->3-->2從0出發(fā)到3的最短路徑為：0-->3從0出發(fā)到4的最短路徑為：0-->3-->2-->4=====================================從0出發(fā)到0的最短距離為：0從0出發(fā)到1的最短距離為：10從0出發(fā)到2的最短距離為：50從0出發(fā)到3的最短距離為：30從0出發(fā)到4的最短距離為：60 |
