前言
dijkstra算法是最短路径算法中为人熟知的一种，是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法，并赋予java实现代码。
一、知识准备：
1、表示图的数据结构
用于存储图的数据结构有多种，本算法中笔者使用的是邻接矩阵。
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
设图g有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
从这个矩阵中，很容易知道图中的信息。
（1）要判断任意两顶点是否有边无边就很容易了；
（2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；
（3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；
而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。
有向图的定义也类似，故不做赘述。
2、单起点全路径
所谓单起点全路径，就是指在一个图中，从一个起点出发，到所有节点的最短路径。
3、图论的基本知识(读者需自行寻找相关资料)
4、互补松弛条件
设标量d1,d2,....,dn满足
dj<=di + aij, (i,j)属于a,
且p是以i1为起点ik为终点的路，如果
dj = di + aij, 对p的所有边(i, j)
成立，那么p是从i1到ik的最短路。其中，满足上面两式的被称为最短路问题的互补松弛条件。
二、算法思想
1、令g = （v，e）为一个带权无向图。g中若有两个相邻的节点,i和j。aij(在这及其后面都表示为下标，请注意)为节点i到节点j的权值，在本算法可以理解为距离。每个节点都有一个值di(节点标记)表示其从起点到它的某条路的距离。
2、算法初始有一个数组v用于储存未访问节点的列表，我们暂称为候选列表。选定节点1为起始节点。开始时，节点1的d1=0, 其他节点di=无穷大，v为所有节点。
初始化条件后，然后开始迭代算法，直到v为空集时停止。具体迭代步骤如下：
将d值最小的节点di从候选列表中移除。(本例中v的数据结构采用的是优先队列实现最小值出列，最好使用斐波那契对，在以前文章有过介绍，性能有大幅提示)。对于以该节点为起点的每一条边，不包括移除v的节点, (i, j)属于a， 若dj > di + aij（违反松弛条件）,则令
dj = di + aij , （如果j已经从v中移除过，说明其最小距离已经计算出，不参与此次计算）
可以看到在算法的运算工程中，节点的d值是单调不增的
具体算法图解如下
三、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
|
public class vertex implements comparable<vertex>{ /** * 节点名称(a,b,c,d) */ private string name; /** * 最短路径长度 */ private int path; /** * 节点是否已经出列(是否已经处理完毕) */ private boolean ismarked; public vertex(string name){ this.name = name; this.path = integer.max_value; //初始设置为无穷大 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 { /* * 顶点 */ private list<vertex> vertexs; /* * 边 */ private int[][] edges; /* * 没有访问的顶点 */ private queue<vertex> unvisited; public graph(list<vertex> vertexs, int[][] edges) { this.vertexs = vertexs; this.edges = edges; initunvisited(); } /* * 搜索各顶点最短路径 */ public void search(){ while(!unvisited.isempty()){ vertex vertex = unvisited.element(); //顶点已经计算出最短路径，设置为"已访问" 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); } } /* * 初始化未访问顶点集合 */ private void initunvisited() { unvisited = new priorityqueue<vertex>(); for (vertex v : vertexs) { unvisited.add(v); } } /* * 从未访问顶点集合中删除已找到最短路径的节点 */ private void pop() { unvisited.poll(); } /* * 获取顶点到目标顶点的距离 */ private int getdistance(vertex source, vertex destination) { int sourceindex = vertexs.indexof(source); int destindex = vertexs.indexof(destination); return edges[sourceindex][destindex]; } /* * 获取顶点所有(未访问的)邻居 */ 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) { //顶点本身，跳过 continue; } distance = edges[position][i]; //到所有顶点的距离 if (distance < integer.max_value) { //是邻居(有路径可达) neighbor = getvertex(i); if (!neighbor.ismarked()) { //如果邻居没有访问过，则加入list; neighbors.add(neighbor); } } } return neighbors; } /* * 根据顶点位置获取顶点 */ 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(); } } |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://www.cnblogs.com/junyuhuang/p/4544747.html
