任務描述：在一個無向圖中，獲取起始節點到所有其他節點的最短路徑描述
dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用open, close表方式
用open,close表的方式，其采用的是貪心法的算法策略，大概過程如下：
1.聲明兩個集合，open和close，open用于存儲未遍歷的節點，close用來存儲已遍歷的節點
2.初始階段，將初始節點放入close，其他所有節點放入open
3.以初始節點為中心向外一層層遍歷，獲取離指定節點最近的子節點放入close并從新計算路徑，直至close包含所有子節點
代碼實例如下：
node對象用于封裝節點信息，包括名字和子節點
java" id="highlighter_373167">
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class node { private string name; private map<node,integer> child=new hashmap<node,integer>(); public node(string name){ this.name=name; } public string getname() { return name; } public void setname(string name) { this.name = name; } public map<node, integer> getchild() { return child; } public void setchild(map<node, integer> child) { this.child = child; }} |
mapbuilder用于初始化數據源，返回圖的起始節點
|
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
|
public class mapbuilder { public node build(set<node> open, set<node> close){ node nodea=new node("a"); node nodeb=new node("b"); node nodec=new node("c"); node noded=new node("d"); node nodee=new node("e"); node nodef=new node("f"); node nodeg=new node("g"); node nodeh=new node("h"); nodea.getchild().put(nodeb, 1); nodea.getchild().put(nodec, 1); nodea.getchild().put(noded, 4); nodea.getchild().put(nodeg, 5); nodea.getchild().put(nodef, 2); nodeb.getchild().put(nodea, 1); nodeb.getchild().put(nodef, 2); nodeb.getchild().put(nodeh, 4); nodec.getchild().put(nodea, 1); nodec.getchild().put(nodeg, 3); noded.getchild().put(nodea, 4); noded.getchild().put(nodee, 1); nodee.getchild().put(noded, 1); nodee.getchild().put(nodef, 1); nodef.getchild().put(nodee, 1); nodef.getchild().put(nodeb, 2); nodef.getchild().put(nodea, 2); nodeg.getchild().put(nodec, 3); nodeg.getchild().put(nodea, 5); nodeg.getchild().put(nodeh, 1); nodeh.getchild().put(nodeb, 4); nodeh.getchild().put(nodeg, 1); open.add(nodeb); open.add(nodec); open.add(noded); open.add(nodee); open.add(nodef); open.add(nodeg); open.add(nodeh); close.add(nodea); return nodea; }} |
圖的結構如下圖所示：
dijkstra對象用于計算起始節點到所有其他節點的最短路徑
|
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
|
public class dijkstra { set<node> open=new hashset<node>(); set<node> close=new hashset<node>(); map<string,integer> path=new hashmap<string,integer>();//封裝路徑距離 map<string,string> pathinfo=new hashmap<string,string>();//封裝路徑信息 public node init(){ //初始路徑,因沒有a->e這條路徑,所以path(e)設置為integer.max_value path.put("b", 1); pathinfo.put("b", "a->b"); path.put("c", 1); pathinfo.put("c", "a->c"); path.put("d", 4); pathinfo.put("d", "a->d"); path.put("e", integer.max_value); pathinfo.put("e", "a"); path.put("f", 2); pathinfo.put("f", "a->f"); path.put("g", 5); pathinfo.put("g", "a->g"); path.put("h", integer.max_value); pathinfo.put("h", "a"); //將初始節點放入close,其他節點放入open node start=new mapbuilder().build(open,close); return start; } public void computepath(node start){ node nearest=getshortestpath(start);//取距離start節點最近的子節點,放入close if(nearest==null){ return; } close.add(nearest); open.remove(nearest); map<node,integer> childs=nearest.getchild(); for(node child:childs.keyset()){ if(open.contains(child)){//如果子節點在open中 integer newcompute=path.get(nearest.getname())+childs.get(child); if(path.get(child.getname())>newcompute){//之前設置的距離大于新計算出來的距離 path.put(child.getname(), newcompute); pathinfo.put(child.getname(), pathinfo.get(nearest.getname())+"->"+child.getname()); } } } computepath(start);//重復執行自己,確保所有子節點被遍歷 computepath(nearest);//向外一層層遞歸,直至所有頂點被遍歷 } public void printpathinfo(){ set<map.entry<string, string>> pathinfos=pathinfo.entryset(); for(map.entry<string, string> pathinfo:pathinfos){ system.out.println(pathinfo.getkey()+":"+pathinfo.getvalue()); } } /** * 獲取與node最近的子節點 */ private node getshortestpath(node node){ node res=null; int mindis=integer.max_value; map<node,integer> childs=node.getchild(); for(node child:childs.keyset()){ if(open.contains(child)){ int distance=childs.get(child); if(distance<mindis){ mindis=distance; res=child; } } } return res; }} |
main用于測試dijkstra對象
|
1
2
3
4
5
6
7
8
|
public class main { public static void main(string[] args) { dijkstra test=new dijkstra(); node start=test.init(); test.computepath(start); test.printpathinfo(); }} |
打印輸出如下：
d:a->d
e:a->f->e
f:a->f
g:a->c->g
b:a->b
c:a->c
h:a->b->h
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/javaman_chen/article/details/8254309
