-
Notifications
You must be signed in to change notification settings - Fork 58
/
WeightShortPath.java
203 lines (175 loc) · 4.76 KB
/
WeightShortPath.java
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
package chapter9.smallestpath;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
/**
* Dijkstra算法求单源头最短路径
*
* @author wenl
*
*/
public class WeightShortPath {
public List<Vertex> graph;
public static class AdjVertex {
Vertex w;
public int cvw;// vw边的权
public AdjVertex(Vertex w, int cvw) {
super();
this.w = w;
this.cvw = cvw;
}
public Vertex getW() {
return w;
}
public void setW(Vertex w) {
this.w = w;
}
public int getCvw() {
return cvw;
}
public void setCvw(int cvw) {
this.cvw = cvw;
}
}
public static class Vertex implements Comparable<Vertex> {
Integer dist;// 到该节点的路径
String name;
List<AdjVertex> adj;
Vertex path;// 最短路径上连接到该节点的父节点
boolean known;
public Vertex getPath() {
return path;
}
public List<AdjVertex> getAdj() {
return adj;
}
public void setAdj(List<AdjVertex> adj) {
this.adj = adj;
}
public boolean isKnown() {
return known;
}
public void setKnown(boolean known) {
this.known = known;
}
public void setPath(Vertex path) {
this.path = path;
}
public Vertex(String name) {
super();
this.name = name;
}
public Integer getDist() {
return dist;
}
public void setDist(Integer dist) {
this.dist = dist;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public int compareTo(Vertex o) {
return this.dist.compareTo(o.dist);
}
}
/**
* 著名的dijkstra算法 解决单源最短路径(权无负值)
*
* @param s
* 起点
*/
public void dijkstra(Vertex s) {
for (Vertex v : graph) {// 初始默认所有顶点未被访问
v.setDist(Integer.MAX_VALUE);
v.known = false;
}
s.dist = 0;// 声明起点的距离为0
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<Vertex>();
// 将s放入优先队列
priorityQueue.add(s);
while (!priorityQueue.isEmpty()) {// 知道所有顶点的最短路径都已知并且优先队列为空
Vertex v = priorityQueue.poll();// 取出未知节点中最短路径最小的节点
if (v != null) {
if (!v.known) {
v.known = true;// 声明该节点已知
if (v.getAdj() != null && !v.getAdj().isEmpty()) {
// 如 dv+cvw<=dw 则更新临接点的最短路径,并且更新值放入到优先队列中
for (AdjVertex adjW : v.getAdj()) {
if (!adjW.getW().known) {
if (v.dist + adjW.cvw < adjW.getW().getDist()) {
adjW.getW().setDist(v.dist + adjW.cvw);
adjW.getW().setPath(v);
priorityQueue.add(adjW.getW());
}
}
}
}
}
}
}
}
public static void main(String[] args) {
List<Vertex> graph = new ArrayList<Vertex>();
Vertex v1 = new Vertex("1");
Vertex v20 = new Vertex("20");
Vertex v21 = new Vertex("21");
Vertex v22 = new Vertex("22");
Vertex v30 = new Vertex("30");
Vertex v31 = new Vertex("31");
Vertex v32 = new Vertex("32");
Vertex v4 = new Vertex("4");
List<AdjVertex> adjV1 = new ArrayList<AdjVertex>();
adjV1.add(new AdjVertex(v20, 1));
adjV1.add(new AdjVertex(v21, 3));
adjV1.add(new AdjVertex(v22, 1));
v1.setAdj(adjV1);
List<AdjVertex> adjV20 = new ArrayList<AdjVertex>();
adjV20.add(new AdjVertex(v30, 1));
adjV20.add(new AdjVertex(v21, 1));
v20.setAdj(adjV20);
List<AdjVertex> adjV21 = new ArrayList<AdjVertex>();
adjV21.add(new AdjVertex(v31, 5));
v21.setAdj(adjV21);
List<AdjVertex> adjV22 = new ArrayList<AdjVertex>();
adjV22.add(new AdjVertex(v32, 2));
v22.setAdj(adjV22);
List<AdjVertex> adjV30 = new ArrayList<AdjVertex>();
List<AdjVertex> adjV31 = new ArrayList<AdjVertex>();
List<AdjVertex> adjV32 = new ArrayList<AdjVertex>();
adjV30.add(new AdjVertex(v31, 1));
adjV31.add(new AdjVertex(v4, 1));
adjV32.add(new AdjVertex(v31, 1));
v30.setAdj(adjV30);
v31.setAdj(adjV31);
v32.setAdj(adjV32);
//
graph.add(v1);
graph.add(v30);
graph.add(v31);
graph.add(v32);
graph.add(v20);
graph.add(v21);
graph.add(v22);
graph.add(v4);
WeightShortPath shortPath = new WeightShortPath();
shortPath.setGraph(graph);
shortPath.dijkstra(v1);
for (Vertex v : shortPath.getGraph()) {
if (v.getPath() != null) {
System.out.println(v.getPath().getName() + "-" + v.getName() + " cost:" + v.getDist());
} else {
System.out.println(v.getName() + "-" + v.getName() + " cost:" + v.getDist());
}
}
}
public List<Vertex> getGraph() {
return graph;
}
public void setGraph(List<Vertex> graph) {
this.graph = graph;
}
}