-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra.java
More file actions
133 lines (110 loc) · 4.3 KB
/
Dijkstra.java
File metadata and controls
133 lines (110 loc) · 4.3 KB
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import SupportData.GraphSearchUtil;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 迪杰斯特拉算法
* 对于带权值的有向无环图,迪杰斯特拉算法能够计算出从给定的起点到终点最短的路径
* 做法如下:
* 维护一个包含从起点到所有节点的权值的数据组;
* 依次从这个数据组中取出权值最小的节点作为基准,遍历这个基准节点所有相连通的节点,比较起点通过这个节点到另外的节点(起点到这个节点的权值+这个节点到其他节点的权值)和当前数据组中起点到另外节点的值的大小;
* 如果通过这个节点到另外节点的权值更小的话,那么就更新数据组中的值.
* 依次更新,直到终点是数据组中未做基准点而且权值最小的点.
* 原理:因为是有向图并且无环,作为基准的点,当时的权值都是起点到这些节点最小的时候.
* 书中解释:找出途中最便宜的节点,并且确保没有到该节点的更便宜的路径.
*
*
*/
public class Dijkstra implements AlgorithmInGraph {
public void showAlgorithm() {
int [][] graph = new int [5][5];
//不可达
for(int i = 0;i<5;i++){
for(int j = 0;j<5;j++){
graph[i][j] = i == j? 0:-1;
}
}
graph[0][1] = 9;
graph[0][2] = 2;
graph[0][3] = 3;
graph[1][3] = 4;
graph[2][4] = 4;
graph[3][2] = 2;
graph[3][4] = 1;
GraphSearchUtil.printGraph(graph);
List<Integer> nodes = doDijkstra(graph,1,0);
if(nodes != null) {
System.out.println(Arrays.toString(nodes.toArray()));
}else{
System.out.println("当前条件起点到终点不可达");
}
}
/**
* 传入一个图的数据的二维数组,图需要是有向图,并且不能有环的存在
* 传入起始节点和终结节点
* 返回节点的list,就是从起点到终点算出来权值最短的路径的节点
* @param graph
* @param start
* @param end
* @return
*/
private List<Integer> doDijkstra(int [][] graph,int start,int end) {
int length = graph.length;
int[] minimumValue = new int[length];
//表示当前不可达
for (int i = 0; i < length; i++) {
minimumValue[i] = Integer.MAX_VALUE;
}
int[] minmimumNode = new int[length];
for(int i=0;i<length;i++){
minmimumNode[i] = -1;
}
List<Integer> examinedNode = new ArrayList<Integer>();
//存放当前最小值的节点
minimumValue[start] = 0;
minmimumNode[start] = start;
int currentNode = start;
int index = 0;
boolean continueSeach = true;
while (continueSeach) {
continueSeach = false;
for (int i = 0; i < length; i++) {
if (graph[currentNode][i] < 0) {
continue;
}
if (graph[currentNode][i] + minimumValue[currentNode] < minimumValue[i]) {
minimumValue[i] = graph[currentNode][i] + minimumValue[currentNode];
minmimumNode[i] = currentNode;
}
}
//已经检查过的节点
examinedNode.add(currentNode);
//从当前节点中选择一个最小的节点值
int minmum = Integer.MAX_VALUE;
for (int i = 0; i < length; i++) {
if (!examinedNode.contains(i) && minimumValue[i] < minmum) {
currentNode = i;
minmum = minimumValue[i];
continueSeach = true;
}
}
}
//不可达
if(minmimumNode[end] == -1){
return null;
}else{
System.out.println(Arrays.toString(minmimumNode));
List<Integer> reversResult = new ArrayList<Integer>();
int node = end;
while(node != start){
reversResult.add(minmimumNode[node]);
node = minmimumNode[node];
}
List<Integer> result = new ArrayList<Integer>();
for(int i = reversResult.size() - 1;i>=0;i--){
result.add(reversResult.get(i));
}
return result;
}
}
}