本文采用java實(shí)現(xiàn)單源最短路徑，并帶有略微詳細(xì)的注解，供大家參考，具體內(nèi)容如下
|
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 來儲存 圖的頂點(diǎn) * 2. 采用 map 來儲存 邊集 ， map 可以 實(shí)現(xiàn) 一對多的關(guān)系， 因此能很好的實(shí)現(xiàn)鄰接表結(jié)構(gòu) * 3. 采用arraylist的原因 是使 邊集有序 這樣， node 的里面 那個(gè)記錄距離的集合才能一一對應(yīng) */public class minpath { private static class graph{ private arraylist<node1> nodes = new arraylist<>(); // 表示圖頂點(diǎn) ， 同時(shí)他也作為v集合 private map<node1, arraylist<node1>> adjanode = new hashmap<>(); // 表示圖的邊 private arraylist<node1> nodes1 ; // 表示s集合, 即存儲已經(jīng)訪問的節(jié)點(diǎn)， private float[] minpath; //用來存儲源點(diǎn)到每個(gè)頂點(diǎn)的距離 float min = float.max_value; /** * @param start * @param end * @param distance * 構(gòu)建鄰接表。使之成為圖 */ 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("頂點(diǎn) ： " + entry.getkey().name + " 鏈接頂點(diǎn)有： "); 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.這個(gè)方法用于初始化s集合 及 初始化距離數(shù)組 * 2. 設(shè)置源點(diǎn)， 并且將源點(diǎn)作為內(nèi)容 初始化算法 */ public void findminpath() { node1 node1 = null; // 用來記錄列表里最小的點(diǎn) nodes1 = new arraylist<>(); // 存儲已經(jīng)遍歷過的點(diǎn) minpath = new float[nodes.size()]; // 初始化距離數(shù)組 int i; /* * 對最短路徑進(jìn)行初始化， 設(shè)置源點(diǎn)到其他地方的值為無窮大 * */ for (i = 0; i < minpath.length; i++) { minpath[i] = float.max_value; } node1 node = nodes.get(0); nodes1.add(node); // 將源點(diǎn)加入 s 集合 node.visited = true; arraylist<node1> n = adjanode.get(node); // 獲取到源點(diǎn)的邊集 /* * 先對源節(jié)點(diǎn)進(jìn)行初始化 * 1. 對 距離數(shù)組進(jìn)行初始化。 * 2. 找到源點(diǎn)到某個(gè)距離最短的點(diǎn)， 并標(biāo)記 * * */ 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); // 找到當(dāng)前最短路徑 } } this.process(node1, min); } private void process(node1 node, float distance ) { min = float.max_value; //作為標(biāo)記 node1 node1 = null; // 同樣記錄距離最短的點(diǎn) int i; arraylist<node1> n = adjanode.get(node); // 獲得邊集 for (i = 0 ; i < n.size(); i++) { if (!n.get(i).visited) { // 這個(gè)邊集里的頂點(diǎn)不在 s 集合里 if (minpath[n.get(i).id] == float.max_value) { minpath[n.get(i).id] = distance + node.distonext.get(i); // 源點(diǎn)到下一點(diǎn)的距離 }else if (distance + node.distonext.get(i) < minpath[n.get(i).id] ) { //源點(diǎn)到該頂點(diǎn)的距離變小了， 則改變 minpath[n.get(i).id] = distance + node.distonext.get(i); // 更新源點(diǎn)到下一個(gè)點(diǎn)的距離 } } } /* * 這個(gè)for 用于找到 距離集合中 距離源點(diǎn)最近 且并未被訪問過的 * 這個(gè)for 同時(shí)可以確保 該節(jié)點(diǎn)確實(shí)可到達(dá) * */ 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); //源點(diǎn)到 當(dāng)前的距離 }else { // 說明此位置沒有后續(xù)節(jié)點(diǎn)， 或者 已經(jīng)全部被訪問完了， 則到達(dá)此位置只需要加上此位置的值 } } } 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); // 下面嘗試一下非連通圖// /**// * 權(quán)值： 1// * a -----------b// * 權(quán) | *// * 值 | * 權(quán)值： 3// * 2 | *// * c-----d// * 權(quán)值： 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("此數(shù)組下標(biāo)代表id，值代表從源點(diǎn)分別到各點(diǎn)的最短距離， a開始的下標(biāo)是0， b、c、d等依次類推， 并且源點(diǎn)默認(rèn)設(shè)置為id為零0的開始"); gp.findminpath(); system.out.println(arrays.tostring(gp.minpath)); }}/** * 頂點(diǎn)類 */class node1{ string name; boolean visited = false; // 訪問狀態(tài)。有效 減少原算法移除v集合中元素所花費(fèi)的時(shí)間 int id = -1; // 設(shè)置默認(rèn)id為-1 arraylist<float> distonext = new arraylist<>(); //這一點(diǎn) 到另外每一個(gè)點(diǎn)的距離 public node1(int id, string name) { this.id = id; this.name = name; }} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/qq_40860649/article/details/81291681
