Java Dijakstra算法的实现。
Dijakstra算法的实现。
实例源码：
源代码：
执行
执行中...
x
1
2
import java.util.ArrayList;3
4
import java.util.Comparator;/*来 自 N o w J a v a . c o m - 时代Java*/5
6
import java.util.HashMap;7
8
import java.util.PriorityQueue;9
10
11
//This is an implementation of Dijakstra algorithm. It computes the single source minimum distances for a positive weighted graph.12
13
public class Dijakstra {14
15
/**16
17
* Computes the minimum distances between s and all the other nodes for a POSITIVE weighted graph.18
19
* @param s int representing the source node number20
21
* @param gWeights it's a matrix V*V where V is the number of verticies. gWeights[u][v] = w if there is an edge between u and v of weight w, gWeights[u][u]=0, gWeights[u][v]=INTEGER.MAX_INT if there is no edge between u and v22
23
* @param gAdjencyList it's an arraylist of size V (where V is the number of verticies) that contains the neighbors for all the nodes. gAdjencyList[u] is a list that contains the nodes v such that there is an edge u->v24
25
* @return the minimal distance from s to every node. The keys are the nodes and the values are the minimum distances26
27
*/28
29
public static HashMap<Integer, Integer> dijakstra(int s,30
31
int[][] gWeights, ArrayList<ArrayList<Integer>> gAdjencyList) {32
33
HashMap<Integer, Integer> nonVisitedNodes = new HashMap<Integer, Integer>(); //contains the non visited nodes as a key and their current computed distance to s as a value34
35
PriorityQueue<int[]> minValue = new PriorityQueue<int[]>(10,36
37
new Comparator<int[]>() {38
39
public int compare(int[] arg0, int[] arg1) {40
41
if (arg0[1] == arg1[1]) {42
43
return new Integer(arg0[0])44
45
.compareTo(new Integer(arg1[0]));46
47
}48
49
return new Integer(arg0[1]).compareTo(new Integer(50
51
arg1[1]));52
53
}/* 来自 时 代 J a v a 公 众 号*/54
55
56
});//will store the minimal value of the non visited nodes. Could optimize runtime if we store the two min values in variables.57
58
59
for (int i = 0; i < gAdjencyList.size(); i++) {60
61
nonVisitedNodes.put(i, Integer.MAX_VALUE);62
63
if (i != s)64
65
minValue.add(new int[] { i, Integer.MAX_VALUE });66
67
} //initialize non visited nodes with infiniy distances68
69
70
HashMap<Integer, Integer> visitedNodes = new HashMap<Integer, Integer>(); //contains the nodes visited as a key and their distances to s as a value. Initially empty71
72
HashMap<Integer, Integer> parents = new HashMap<Integer, Integer>(); //contains the nodes as a key and the parent node in the optimal path from s as a value.73
74
75
//start with the node s.76
77
minValue.add(new int[] { s, 0 });78
79
parents.put(s, null);80
81
82
while (!nonVisitedNodes.isEmpty()) {83
84
//visit the node that has the current minimal distance85
86
int currentNode = minValue.peek()[0];87
88
int value = minValue.poll()[1];89
90
visitedNodes.put(currentNode, value);91
92
nonVisitedNodes.remove(currentNode);93
94
//update the distance of all his non visited neighbors95
96
for (int i = 0; i < gAdjencyList.get(currentNode).size(); i++) {97
98
int neighbor = gAdjencyList.get(currentNode).get(i);99
100
if (nonVisitedNodes.containsKey(neighbor)101
102
&& value + gWeights[currentNode][neighbor] < nonVisitedNodes103
104
.get(neighbor)) {105
106
int neighValue = value107
108
+ gWeights[currentNode][neighbor];109
110
nonVisitedNodes.put(neighbor, neighValue);111
112
minValue.add(new int[] { neighbor, neighValue });113
114
parents.put(neighbor, currentNode);115
116
}117
118
}119
120
}121
122
return visitedNodes;123
124
}125
126
127
public static void main(String[] args) {128
129
int[][] gWeights = new int[][] { { 0, 5, -1, 9, 0, 2 },130
131
{ 5, 0, 2, -1, -1, -1 }, { -1, 2, 0, 3, -1, -1 },132
133
{ 9, -1, 3, 0, 2, -1 }, { -1, -1, -1, 2, 0, 3 },134
135
{ 2, -1, -1, -1, 3, 0 } };136
137
138
ArrayList<ArrayList<Integer>> gAdjency = new ArrayList<ArrayList<Integer>>();139
140
ArrayList<Integer> neighbors0 = new ArrayList<Integer>();141
142
neighbors0.add(1);143
144
neighbors0.add(3);145
146
neighbors0.add(5);147
148
ArrayList<Integer> neighbors1 = new ArrayList<Integer>();149
150
neighbors1.add(0);151
152
neighbors1.add(2);153
154
ArrayList<Integer> neighbors2 = new ArrayList<Integer>();155
156
neighbors2.add(1);157
158
neighbors2.add(3);159
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java