前言
dijkstra算法是最短路徑算法中為人熟知的一種，是單起點(diǎn)全路徑算法。該算法被稱為是“貪心算法”的成功典范。本文接下來將嘗試以最通俗的語言來介紹這個(gè)偉大的算法，并賦予java實(shí)現(xiàn)代碼。
一、知識(shí)準(zhǔn)備：
1、表示圖的數(shù)據(jù)結(jié)構(gòu)
用于存儲(chǔ)圖的數(shù)據(jù)結(jié)構(gòu)有多種，本算法中筆者使用的是鄰接矩陣。
圖的鄰接矩陣存儲(chǔ)方式是用兩個(gè)數(shù)組來表示圖。一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息，一個(gè)二維數(shù)組（鄰接矩陣）存儲(chǔ)圖中的邊或弧的信息。
設(shè)圖g有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n*n的方陣，定義為：
從上面可以看出，無向圖的邊數(shù)組是一個(gè)對(duì)稱矩陣。所謂對(duì)稱矩陣就是n階矩陣的元滿足aij = aji。即從矩陣的左上角到右下角的主對(duì)角線為軸，右上角的元和左下角相對(duì)應(yīng)的元全都是相等的。
從這個(gè)矩陣中，很容易知道圖中的信息。
（1）要判斷任意兩頂點(diǎn)是否有邊無邊就很容易了；
（2）要知道某個(gè)頂點(diǎn)的度，其實(shí)就是這個(gè)頂點(diǎn)vi在鄰接矩陣中第i行或（第i列）的元素之和；
（3）求頂點(diǎn)vi的所有鄰接點(diǎn)就是將矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點(diǎn)；
而有向圖講究入度和出度，頂點(diǎn)vi的入度為1，正好是第i列各數(shù)之和。頂點(diǎn)vi的出度為2，即第i行的各數(shù)之和。
有向圖的定義也類似，故不做贅述。
2、單起點(diǎn)全路徑
所謂單起點(diǎn)全路徑，就是指在一個(gè)圖中，從一個(gè)起點(diǎn)出發(fā)，到所有節(jié)點(diǎn)的最短路徑。
3、圖論的基本知識(shí)(讀者需自行尋找相關(guān)資料)
4、互補(bǔ)松弛條件
設(shè)標(biāo)量d1,d2,....,dn滿足
dj<=di + aij, (i,j)屬于a,
且p是以i1為起點(diǎn)ik為終點(diǎn)的路，如果
dj = di + aij, 對(duì)p的所有邊(i, j)
成立，那么p是從i1到ik的最短路。其中，滿足上面兩式的被稱為最短路問題的互補(bǔ)松弛條件。
二、算法思想
1、令g = （v，e）為一個(gè)帶權(quán)無向圖。g中若有兩個(gè)相鄰的節(jié)點(diǎn),i和j。aij(在這及其后面都表示為下標(biāo)，請(qǐng)注意)為節(jié)點(diǎn)i到節(jié)點(diǎn)j的權(quán)值，在本算法可以理解為距離。每個(gè)節(jié)點(diǎn)都有一個(gè)值di(節(jié)點(diǎn)標(biāo)記)表示其從起點(diǎn)到它的某條路的距離。
2、算法初始有一個(gè)數(shù)組v用于儲(chǔ)存未訪問節(jié)點(diǎn)的列表，我們暫稱為候選列表。選定節(jié)點(diǎn)1為起始節(jié)點(diǎn)。開始時(shí)，節(jié)點(diǎn)1的d1=0, 其他節(jié)點(diǎn)di=無窮大，v為所有節(jié)點(diǎn)。
初始化條件后，然后開始迭代算法，直到v為空集時(shí)停止。具體迭代步驟如下：
將d值最小的節(jié)點(diǎn)di從候選列表中移除。(本例中v的數(shù)據(jù)結(jié)構(gòu)采用的是優(yōu)先隊(duì)列實(shí)現(xiàn)最小值出列，最好使用斐波那契對(duì)，在以前文章有過介紹，性能有大幅提示)。對(duì)于以該節(jié)點(diǎn)為起點(diǎn)的每一條邊，不包括移除v的節(jié)點(diǎn), (i, j)屬于a， 若dj > di + aij（違反松弛條件）,則令
dj = di + aij , （如果j已經(jīng)從v中移除過，說明其最小距離已經(jīng)計(jì)算出，不參與此次計(jì)算）
可以看到在算法的運(yùn)算工程中，節(jié)點(diǎn)的d值是單調(diào)不增的
具體算法圖解如下
三、java代碼實(shí)現(xiàn)
|
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
|
public class vertex implements comparable<vertex>{ /** * 節(jié)點(diǎn)名稱(a,b,c,d) */ private string name; /** * 最短路徑長度 */ private int path; /** * 節(jié)點(diǎn)是否已經(jīng)出列(是否已經(jīng)處理完畢) */ private boolean ismarked; public vertex(string name){ this.name = name; this.path = integer.max_value; //初始設(shè)置為無窮大 this.setmarked(false); } public vertex(string name, int path){ this.name = name; this.path = path; this.setmarked(false); } @override public int compareto(vertex o) { return o.path > path?-1:1; }} |
|
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
|
public class graph { /* * 頂點(diǎn) */ private list<vertex> vertexs; /* * 邊 */ private int[][] edges; /* * 沒有訪問的頂點(diǎn) */ private queue<vertex> unvisited; public graph(list<vertex> vertexs, int[][] edges) { this.vertexs = vertexs; this.edges = edges; initunvisited(); } /* * 搜索各頂點(diǎn)最短路徑 */ public void search(){ while(!unvisited.isempty()){ vertex vertex = unvisited.element(); //頂點(diǎn)已經(jīng)計(jì)算出最短路徑，設(shè)置為"已訪問" vertex.setmarked(true); //獲取所有"未訪問"的鄰居 list<vertex> neighbors = getneighbors(vertex); //更新鄰居的最短路徑 updatesdistance(vertex, neighbors); pop(); } system.out.println("search over"); } /* * 更新所有鄰居的最短路徑 */ private void updatesdistance(vertex vertex, list<vertex> neighbors){ for(vertex neighbor: neighbors){ updatedistance(vertex, neighbor); } } /* * 更新鄰居的最短路徑 */ private void updatedistance(vertex vertex, vertex neighbor){ int distance = getdistance(vertex, neighbor) + vertex.getpath(); if(distance < neighbor.getpath()){ neighbor.setpath(distance); } } /* * 初始化未訪問頂點(diǎn)集合 */ private void initunvisited() { unvisited = new priorityqueue<vertex>(); for (vertex v : vertexs) { unvisited.add(v); } } /* * 從未訪問頂點(diǎn)集合中刪除已找到最短路徑的節(jié)點(diǎn) */ private void pop() { unvisited.poll(); } /* * 獲取頂點(diǎn)到目標(biāo)頂點(diǎn)的距離 */ private int getdistance(vertex source, vertex destination) { int sourceindex = vertexs.indexof(source); int destindex = vertexs.indexof(destination); return edges[sourceindex][destindex]; } /* * 獲取頂點(diǎn)所有(未訪問的)鄰居 */ private list<vertex> getneighbors(vertex v) { list<vertex> neighbors = new arraylist<vertex>(); int position = vertexs.indexof(v); vertex neighbor = null; int distance; for (int i = 0; i < vertexs.size(); i++) { if (i == position) { //頂點(diǎn)本身，跳過 continue; } distance = edges[position][i]; //到所有頂點(diǎn)的距離 if (distance < integer.max_value) { //是鄰居(有路徑可達(dá)) neighbor = getvertex(i); if (!neighbor.ismarked()) { //如果鄰居沒有訪問過，則加入list; neighbors.add(neighbor); } } } return neighbors; } /* * 根據(jù)頂點(diǎn)位置獲取頂點(diǎn) */ private vertex getvertex(int index) { return vertexs.get(index); } /* * 打印圖 */ public void printgraph() { int vernums = vertexs.size(); for (int row = 0; row < vernums; row++) { for (int col = 0; col < vernums; col++) { if(integer.max_value == edges[row][col]){ system.out.print("x"); system.out.print(" "); continue; } system.out.print(edges[row][col]); system.out.print(" "); } system.out.println(); } }} |
|
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
|
public class test { public static void main(string[] args){ list<vertex> vertexs = new arraylist<vertex>(); vertex a = new vertex("a", 0); vertex b = new vertex("b"); vertex c = new vertex("c"); vertex d = new vertex("d"); vertex e = new vertex("e"); vertex f = new vertex("f"); vertexs.add(a); vertexs.add(b); vertexs.add(c); vertexs.add(d); vertexs.add(e); vertexs.add(f); int[][] edges = { {integer.max_value,6,3,integer.max_value,integer.max_value,integer.max_value}, {6,integer.max_value,2,5,integer.max_value,integer.max_value}, {3,2,integer.max_value,3,4,integer.max_value}, {integer.max_value,5,3,integer.max_value,5,3}, {integer.max_value,integer.max_value,4,5,integer.max_value,5}, {integer.max_value,integer.max_value,integer.max_value,3,5,integer.max_value} }; graph graph = new graph(vertexs, edges); graph.printgraph(); graph.search(); } } |
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://www.cnblogs.com/junyuhuang/p/4544747.html
