本文采用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
