本文采用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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
package com.qf.greaph;import java.util.arraylist;import java.util.arrays;import java.util.hashmap;import java.util.map;import java.util.map.entry;/** * @author jiayoo * 7 / 30 * dijkstra最短路径算法是一种单源最短路径 * 本文采用的是邻接表表示图。 * * 图的表示： 1. 采用 arraylist 来储存 图的顶点 * 2. 采用 map 来储存 边集 ， map 可以 实现 一对多的关系， 因此能很好的实现邻接表结构 * 3. 采用arraylist的原因 是使 边集有序 这样， node 的里面 那个记录距离的集合才能一一对应 */public class minpath { private static class graph{ private arraylist<node1> nodes = new arraylist<>(); // 表示图顶点 ， 同时他也作为v集合 private map<node1, arraylist<node1>> adjanode = new hashmap<>(); // 表示图的边 private arraylist<node1> nodes1 ; // 表示s集合, 即存储已经访问的节点， private float[] minpath; //用来存储源点到每个顶点的距离 float min = float.max_value; /** * @param start * @param end * @param distance * 构建邻接表。使之成为图 */ public void addadjanode(node1 start, node1 end, float distance) { if (!nodes.contains(start)) { nodes.add(start); } if (!nodes.contains(end)) { nodes.add(end); } if (adjanode.containskey(start) && adjanode.get(start).contains(end)) { return ; } if (adjanode.containskey(start)) { adjanode.get(start).add(end); }else { arraylist<node1> node = new arraylist<node1>(); node.add(end); adjanode.put(start, node); } start.distonext.add(distance); } /** * 将图打印出来 */ public void pringraph() { if (nodes == null || adjanode == null) { system.out.println("图为空"); return ; } for (entry<node1, arraylist<node1>> entry : adjanode.entryset()) { system.out.println("顶点 ： " + entry.getkey().name + " 链接顶点有： "); for(int i = 0; i < entry.getvalue().size(); i++) { system.out.print(entry.getvalue().get(i).name + " " + "距离是： " + entry.getkey().distonext.get(i) + ", "); } system.out.println(); } } /** * 1.这个方法用于初始化s集合 及 初始化距离数组 * 2. 设置源点， 并且将源点作为内容 初始化算法 */ public void findminpath() { node1 node1 = null; // 用来记录列表里最小的点 nodes1 = new arraylist<>(); // 存储已经遍历过的点 minpath = new float[nodes.size()]; // 初始化距离数组 int i; /* * 对最短路径进行初始化， 设置源点到其他地方的值为无穷大 * */ for (i = 0; i < minpath.length; i++) { minpath[i] = float.max_value; } node1 node = nodes.get(0); nodes1.add(node); // 将源点加入 s 集合 node.visited = true; arraylist<node1> n = adjanode.get(node); // 获取到源点的边集 /* * 先对源节点进行初始化 * 1. 对 距离数组进行初始化。 * 2. 找到源点到某个距离最短的点， 并标记 * * */ for (i = 0; i < n.size(); i++) { minpath[n.get(i).id] = node.distonext.get(i); // 最短路径记录 if (min > node.distonext.get(i)) { min = node.distonext.get(i); node1 = n.get(i); // 找到当前最短路径 } } this.process(node1, min); } private void process(node1 node, float distance ) { min = float.max_value; //作为标记 node1 node1 = null; // 同样记录距离最短的点 int i; arraylist<node1> n = adjanode.get(node); // 获得边集 for (i = 0 ; i < n.size(); i++) { if (!n.get(i).visited) { // 这个边集里的顶点不在 s 集合里 if (minpath[n.get(i).id] == float.max_value) { minpath[n.get(i).id] = distance + node.distonext.get(i); // 源点到下一点的距离 }else if (distance + node.distonext.get(i) < minpath[n.get(i).id] ) { //源点到该顶点的距离变小了， 则改变 minpath[n.get(i).id] = distance + node.distonext.get(i); // 更新源点到下一个点的距离 } } } /* * 这个for 用于找到 距离集合中 距离源点最近 且并未被访问过的 * 这个for 同时可以确保 该节点确实可到达 * */ for (i = 1; i < minpath.length; i++) { if (!nodes.get(i).visited) { if (min > minpath[i] ) { min = minpath[i]; node1 = nodes.get(i); } } } if (node1 != null) { node1.visited = true; process(node1, min); //源点到 当前的距离 }else { // 说明此位置没有后续节点， 或者 已经全部被访问完了， 则到达此位置只需要加上此位置的值 } } } public static void main(string[] args) { node1 n1 = new node1(0,"a"); node1 n2 = new node1(1,"b"); node1 n3 = new node1(2,"c"); node1 n4 = new node1(3,"d"); node1 n5 = new node1(4,"e"); node1 n6 = new node1(5,"f"); graph gp = new graph(); gp.addadjanode(n1, n2, 6); gp.addadjanode(n2, n1, 6); gp.addadjanode(n1, n3, 3); gp.addadjanode(n3, n1, 3); gp.addadjanode(n2, n3, 2); gp.addadjanode(n3, n2, 2); gp.addadjanode(n2, n4, 5); gp.addadjanode(n4, n2, 5); gp.addadjanode(n3, n4, 3); gp.addadjanode(n4, n3, 3); gp.addadjanode(n3, n5, 4); gp.addadjanode(n5, n3, 4); gp.addadjanode(n4, n5, 2); gp.addadjanode(n5, n4, 2); gp.addadjanode(n4, n6, 3); gp.addadjanode(n6, n4, 3); gp.addadjanode(n5, n6, 5); gp.addadjanode(n6, n5, 5); // 下面尝试一下非连通图// /**// * 权值： 1// * a -----------b// * 权 | *// * 值 | * 权值： 3// * 2 | *// * c-----d// * 权值： 5// * // * // * */// // gp.addadjanode(n1, n2, 1);// gp.addadjanode(n2, n1, 1);// // gp.addadjanode(n1, n3, 2);// gp.addadjanode(n3, n1, 2);// // gp.addadjanode(n1, n4, 3);// gp.addadjanode(n4, n1, 3);// // gp.addadjanode(n3, n4, 5);// gp.addadjanode(n4, n3, 5); gp.pringraph(); system.out.println("--------------------------------------------------------------------"); system.out.println("此数组下标代表id，值代表从源点分别到各点的最短距离， a开始的下标是0， b、c、d等依次类推， 并且源点默认设置为id为零0的开始"); gp.findminpath(); system.out.println(arrays.tostring(gp.minpath)); }}/** * 顶点类 */class node1{ string name; boolean visited = false; // 访问状态。有效 减少原算法移除v集合中元素所花费的时间 int id = -1; // 设置默认id为-1 arraylist<float> distonext = new arraylist<>(); //这一点 到另外每一个点的距离 public node1(int id, string name) { this.id = id; this.name = name; }} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_40860649/article/details/81291681
