朝小闇的博客

海上月是天上月,眼前人是心上人

Dijkstra

Dijkstra算法

简要介绍

  • Dijkstra算法是一种广度优先搜索算法
  • 主要解决赋权值有向图或无向图的单源点最短路径问题
  • 时间复杂度是${n^2}$;
  • 权值必须为正;

主要思想

  1. 设置两个顶点集S和T,集合S中存放已经找到最短路径的顶点,集合T中存放尚未找到最短路径的顶点;
  2. 初始状态下,集合S中只包含源点V,集合T中包含除源点之外的所有顶点,此时源点到各顶点的最短路径为两个顶点所连边上的权值,如果没有边,则最小路径为无穷大(代码中设置为最大正整数);
  3. 依次从集合T中选取到源点V路径最短的顶点${v_i}$放入集合S中;
  4. 修改从源点V到T中顶点的最短路径长度;
  5. 循环上面两项直到顶点集T为空;

实例演示:

img

基于邻接矩阵实现算法

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
// 基于邻接矩阵实现无向图最短路径算法
public class Adjacent_Matrix {
// 顶点总个数
private static int numOfVexs = 6;
// 存放各顶点之间的距离
private static int[][] edges = {{0,0,10,0,30,100},
{0,0,5,0,0,0},
{10,5,0,50,0,0},
{0,0,50,0,20,10},
{30,0,0,20,0,60},
{100,0,0,10,60,0}};
// 最短路径源点及终点,取数组下标索引
private static int vertexS = 0;
private static int vertexE = 5;

public static void main(String[] args) {
// 传入源点
int[] distance = dijkstra(vertexS);
System.out.println("源点到各顶点之间的最短路径:");
for (int i = 0; i < distance.length; i++) {
System.out.println("1-"+(i+1)+":");
System.out.println(distance[i]);
}
System.out.println("源点"+(vertexS+1)+"到终点"+(vertexE+1)+"之间的最短路径为:"+distance[vertexE]);
}

public static int[] dijkstra(int v) { //传入源点
if (v < 0 || v >= numOfVexs) {
throw new ArrayIndexOutOfBoundsException();
}
// 默认初始为false,表示在T集合(未找到最短路径)中,true时表示在S集合(已找到源点到目标定点最短路径)中
boolean[] st = new boolean[numOfVexs];
// 存放源点到其他点的矩离
int[] distance = new int[numOfVexs];
// 更新edges二维数组,除自身外将所有距离为0转化为无穷大(即最大正整数)
for (int i = 0; i < numOfVexs; i++) {
for (int j = i + 1; j < numOfVexs; j++) {
if (edges[i][j] == 0) {
edges[i][j] = Integer.MAX_VALUE;
edges[j][i] = Integer.MAX_VALUE;
}
}
}
// 对传入源点与其它顶点之间进行距离初始化
for (int i = 0; i < numOfVexs; i++) {
distance[i] = edges[v][i];
}
// 初始化S集合,将源点v加入S集合
st[v] = true;
// 处理从源点到其余顶点的最短路径
for (int i = 0; i < numOfVexs; ++i) {
int min = Integer.MAX_VALUE;
// 索引号,如果找到最短路径则赋值为目的顶点号
int index=-1;
// 比较从源点到其余顶点的路径长度
for (int j = 0; j < numOfVexs; ++j) {
// 从源点到j顶点的最短路径还没有找到
if (st[j]==false) {
// 从源点到j顶点的路径长度最小
if (distance[j] < min) {
index = j;
min = distance[j];
}
}
}
// 找到源点到索引为index顶点的最短路径长度,将该顶点加入到S集合中
if(index!=-1) {
st[index] = true;
}
// 更新当前最短路径及距离
for (int w = 0; w < numOfVexs; w++) {
if (st[w] == false) {
if (edges[index][w] != Integer.MAX_VALUE
&& (min + edges[index][w] < distance[w])) {
distance[w] = min + edges[index][w];
}
}
}
}
return distance;
}
}

>>
源点到各顶点之间的最短路径:
1-1:
0
1-2:
15
1-3:
10
1-4:
50
1-5:
30
1-6:
60
源点1到终点6之间的最短路径为:60

基于邻接表实现算法

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
//基于邻接表实现算法
public class Adjacency_List {
// 顶点总个数
private static int numOfVexs = 6;
// 对每个顶点创建一个邻接表
private static ENode[] vexs = new ENode[numOfVexs];

// 存放各顶点之间的距离/权值
private static int[][] edges = {{0,0,10,0,30,100},
{0,0,5,0,0,0},
{10,5,0,50,0,0},
{0,0,50,0,20,10},
{30,0,0,20,0,60},
{100,0,0,10,60,0}};
// 最短路径源点及终点,取数组下标索引
private static int vertexS = 0;
private static int vertexE = 5;

public static void main(String[] args) {
init();
// 传入源点
int[] distance = dijkstra(vertexS);
System.out.println("源点到各顶点之间的最短路径:");
for (int i = 0; i < distance.length; i++) {
System.out.println("1-"+(i+1)+":");
System.out.println(distance[i]);
}
System.out.println("源点"+(vertexS+1)+"到终点"+(vertexE+1)+"之间的最短路径为:"+distance[vertexE]);
}

public static void init(){
// 用来临时存储邻接表中的元素
ENode vex;
for (int i = 0; i < numOfVexs; i++) {
// 初始化每一个顶点
vexs[i] = new ENode();
vexs[i].setAdjvex(i);
// 设置其下一个链接和第一个链接为null
vexs[i].setNextadj(null);

// 权值不为0,则
for (int j = 0; j < numOfVexs; j++) {
if(edges[i][j]!=0){
// 每次重新初始化一个地址空间
vex = new ENode();
// 显示内存地址,判断每次地址是否不一样
System.out.println(System.identityHashCode(vex));
// 设置权值和序号
vex.setAdjvex(j);
vex.setWeight(edges[i][j]);

// 将vex的下一个链接设置为vexs[i]的下一个链接,并将vexs[i]的下一个链接设置为vex自身
vex.setNextadj(vexs[i].getNextadj());
vexs[i].setNextadj(vex);
}
}
}
for (int i = 0; i < numOfVexs; i++) {
System.out.println(vexs[i]);
}
}

public static int[] dijkstra(int v) {
if (v < 0 || v >= numOfVexs) {
throw new ArrayIndexOutOfBoundsException();
}
// 默认初始为false,表示在T集合(未找到最短路径)中,true时表示在S集合(已找到源点到目标定点最短路径)中
boolean[] st = new boolean[numOfVexs];
// 存放源点到其他点的距离
int[] distance = new int[numOfVexs];
// 对传入源点与其它顶点之间进行距离初始化,初始化为无穷大(即最大正整数)
for (int i = 0; i < numOfVexs; i++) {
distance[i] = Integer.MAX_VALUE;
}
// 创建源点的ENode类
ENode current;
current = vexs[v].getNextadj();
while (current != null) {
distance[current.getAdjvex()] = current.getWeight();
current = current.getNextadj();
}
// 顶点自身到自身距离为0
distance[v] = 0;
// 初始化S集合,将源点v加入S集合
st[v] = true;
// 处理从源点到其余顶点的最短路径
for (int i = 0; i < numOfVexs; i++) {
int min = Integer.MAX_VALUE;
int index = -1;
// 比较从源点到其余顶点的路径长度
for (int j = 0; j < numOfVexs; j++) {
// 从源点到j顶点的最短路径还没有找到
if (st[j] == false) {
// 从源点到j顶点的路径长度最小
if (distance[j] < min) {
index = j;
min = distance[j];
}
}
}
// 找到源点到索引为index顶点的最短路径长度
if (index != -1) {
st[index] = true;
}
// 更新当前最短路径及距离
for (int w = 0; w < numOfVexs; w++) {
if (st[w] == false) {
current = vexs[w].getNextadj();
while (current != null) {
if (current.getAdjvex() == index) {
if ((min + current.getWeight()) < distance[w]) {
distance[w] = min + current.getWeight();
break;
}
}
current = current.getNextadj();
}
}
}
}
return distance;
}
}

class ENode{
// 源点到当前顶点权值(即距离)
private int weight;
// 当前顶点序号
private int adjvex;
// 下一个节点
private ENode nextadj;

public int getWeight() {
return weight;
}

public void setWeight(int weight) {
this.weight = weight;
}

public int getAdjvex() {
return adjvex;
}

public void setAdjvex(int adjvex) {
this.adjvex = adjvex;
}

public ENode getNextadj() {
return nextadj;
}

public void setNextadj(ENode nextadj) {
this.nextadj = nextadj;
}

@Override
public String toString() {
return "ENode{" +
"weight=" + weight +
", adjvex=" + adjvex +
", nextadj=" + nextadj +
'}';
}
}

>>
356573597
1735600054
21685669
2133927002
1836019240
325040804
1173230247
856419764
621009875
1265094477
2125039532
312714112
692404036
1554874502
1846274136
1639705018
ENode{weight=0, adjvex=0, nextadj=ENode{weight=100, adjvex=5, nextadj=ENode{weight=30, adjvex=4, nextadj=ENode{weight=10, adjvex=2, nextadj=null}}}}
ENode{weight=0, adjvex=1, nextadj=ENode{weight=5, adjvex=2, nextadj=null}}
ENode{weight=0, adjvex=2, nextadj=ENode{weight=50, adjvex=3, nextadj=ENode{weight=5, adjvex=1, nextadj=ENode{weight=10, adjvex=0, nextadj=null}}}}
ENode{weight=0, adjvex=3, nextadj=ENode{weight=10, adjvex=5, nextadj=ENode{weight=20, adjvex=4, nextadj=ENode{weight=50, adjvex=2, nextadj=null}}}}
ENode{weight=0, adjvex=4, nextadj=ENode{weight=60, adjvex=5, nextadj=ENode{weight=20, adjvex=3, nextadj=ENode{weight=30, adjvex=0, nextadj=null}}}}
ENode{weight=0, adjvex=5, nextadj=ENode{weight=60, adjvex=4, nextadj=ENode{weight=10, adjvex=3, nextadj=ENode{weight=100, adjvex=0, nextadj=null}}}}
源点到各顶点之间的最短路径:
1-1:
0
1-2:
15
1-3:
10
1-4:
50
1-5:
30
1-6:
60
源点1到终点6之间的最短路径为:60

思考

  1. System.out.println(System.identityHashCode(vex));输出对象的内存地址;
  2. ENode类创建对象数组和初始化时,先创建对象数组,然后初始化对象数组,再对数组中每一个对象初始化分配内存;

参考博客:https://blog.csdn.net/qq_38410730/article/details/79587768

-------- 本文结束 感谢阅读 --------