数据结构-图的最短路径算法实现

(三)寻找图的最短路径

最短路径

顾名思义,最短路径问题就是在图中的一点寻找到达另一点的最小权值之和(即最短路径)的问题,下面介绍的Dijkstra算法是一种按长度递增次序产生最短路径的算法。

Dijkstra算法

算法思想

  1. 设置两个顶点集合S和T,集合S中存放已经找到最短路径的顶点,集合T中存放当前还未找到最短路径的顶点。
  2. 初始状态时,集合S中只包含原点V1,T中为除原点外的其余顶点:此时原点到各顶点的最短路径为两个顶点上的权值,如果原点V1到该顶点没有边,则最短路径为无穷大。
  3. 从集合T中选取到原点V1的路径长度最短的顶点Vi加入集合S中。
  4. 修改原点V1到集合T中剩余顶点Vj的最短路径长度:新的最短路径长度值为①Vj原来的最短路径长度值与②顶点Vi的最短路径长度加上Vi到Vj的路径长度的较小值。
  5. 不断重复过程步骤(3)和(4),直到集合T的顶点全部加入集合S为止。

求解过程

以上图为例,设顶点V1为开始顶点,从它开始到所有其他顶点被确定。并且顶点V1,V2,V3,V4,V5,V6对应index的0,1,2,3,4,5。除此之外,设置一个一维数组st来标记找到最短路径的顶点的状态,并规定:(1)st[i]=0:未找到原点到Vi顶点的最短途径,表示T集合。(2)st[i]=1:已找到原点到Vi顶点的最短途径,表示S集合。再设置一个一维数组distance,用它来存储从V1到其他顶点的距离,该距离可能是直接的或者间接的,这对应于上面算法思想中的第四条,这里详细介绍一下求解过程:

  1. 初始化数组distance和st,如下图a所示。

  2. (算法第三步)从未访问顶点中选择路径长度最短的顶点加入访问集合。满足st[index] = 0 条件的index可取值{1,2,3,4,5},然后分析图a中的distance数组,可知当index取值为3时,distance[3] = 10,在所有未访问顶点对应的距离最短,所以将st[3]设为1,如下图b所示。

  3. (算法第四步)修改未访问顶点的最短路径。满足st[index] = 0 条件的index可取值{1,2,4,5},判断distance[index]是否小于distance[3]+matrix[3,index],如果不是,则distance[index] = distance[3]+matrix[3,index]。

    1. index = 1:distance[1]为20,distance[3] + matrix[3,1] = 10 + ∞ = ∞,前者小于后者,不用修改。
    2. index = 2:distance[2]为∞,distance[3] + matrix[3,2] = 10 + 20= 30,两者取小者,因此修改distance[2] = 30。
    3. index = 4:distance[4]为∞,distance[3] + matrix[3,4] = 10 + 15 = 25,两者取小者,因此修改distance[4] = 25。
    4. index = 5:distance[5]为∞,distance[3] + matrix[3,5] = 10 + ∞ = ∞,两者相等,不用修改。

    此次操作后,distance发生变化,如下图 c 所示。

  4. (算法第三步)再次从未访问顶点中选择路径长度最短的顶点加入访问集合。满足st[index] = 0 条件的index可取值{1,2,4,5},然后分析图 c 中的distance数组,可知当index取值为1时,distance[1] = 20,在所有未访问顶点对应的距离最短,所以将st[1]设为1,如下图 d 所示。

  5. (算法第四步)修改未访问顶点的最短路径。满足st[index] = 0 条件的index可取值{2,4,5},判断distance[index]是否小于distance[1] + matrix[1,index],如果不是,则distance[index] = distance[1] + matrix[1,index]。

    1. index = 2:distance[2] = 30,distance[1] + matrix[1,2] = 20 + 10 = 30,两者相等,因此不用修改。
    2. index = 4:distance[4] = 25,distance[1] + matrix[1,4] = 20 + ∞ = 25,两者取小者,因此不用修改。
    3. index = 5:distance[5] = ∞,distance[1] + matrix[1,5] = 20 + ∞ = ∞,两者相等,不用修改。

    此次操作后,distance的状态无变化,因此还是图 d。

  6. (算法第三步)再次从未访问顶点中选择路径长度最短的顶点加入访问集合。满足st[index] = 0 条件的index可取值{2,4,5},然后分析图 d 中的distance数组,可知当index取值为4时,distance[4] = 25,在所有未访问顶点对应的距离最短,所以将st[4]设为1,如下图 e 所示。

  7. (算法第四步)修改未访问顶点的最短路径。满足st[index] = 0 条件的index可取值{2,5},判断distance[index]是否小于distance[1] + matrix[1,index],如果不是,则distance[index] = distance[1] + matrix[1,index]。

    1. index = 2:distance[2] = 30,distance[4] + matrix[4,2] = 25 + 25 = 50,两者取小者为前者,因此不用修改。
    2. index = 5:distance[5] = ∞,distance[4] + matrix[4,5] = 25 + ∞ = ∞,两者相等,不用修改。

    此次操作后,distance的状态无变化,因此还是图 e。

  8. (算法第三步)再次从未访问顶点中选择路径长度最短的顶点加入访问集合。满足st[index] = 0 条件的index可取值{2,5},然后分析图 e 中的distance数组,可知当index取值为2时,distance[2] = 30,在所有未访问顶点对应的距离最短,所以将st[2]设为1,如下图 f 所示。

  9. (算法第四步)修改未访问顶点的最短路径。满足st[index] = 0 条件的index可取值{5},index = 5:distance[5] = ∞,distance[2] + matrix[2,5] = 30 + 5 = 35,前者大于后者,修改distance[5] = 35,如下图g所示。

  10. (算法第三步)再次从未访问顶点中选择路径长度最短的顶点加入访问集合。满足st[index] = 0 条件的index可取值{5},然后分析图 e 中的distance数组,可知当index取值为2时,distance[5] = 35,在所有未访问顶点对应的距离最短,所以将st[5]设为1,如下图 h 所示。

  11. (算法第四步)至此之后,集合T的顶点已经全部加入集合S中,程序结束。

代码实现

基于邻接矩阵的代码实现:

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
//实现Dijkstra算法
public int[] dijkstra(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
boolean[] st = new boolean[numOfVexs]; //默认初始值为false
int[] distance = new int[numOfVexs]; //存放原点到其他点的距离

for(int i = 0;i < numOfVexs;i++){
for(int j=0;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];
}
st[v] = true;
distance[v] = 0;
//循环开始
for(int i=0;i<numOfVexs;i++){
int min = Integer.MAX_VALUE;
int index = -1;
//取最小值
for(int j=0;j<numOfVexs;j++){
if(st[j]==false){
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){
if(edges[index][w]!= Integer.MAX_VALUE &&
(min + edges[index][w]<distance[w])){
distance[w] = min + edges[index][w];
}
}
}

}
return distance;
}

基于邻接表的代码实现:

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
public int[] dijkstra(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
boolean[] st = new boolean[numOfVexs];
int[] distance = new int[numOfVexs];
//初始化
ENode current = vexs[v].firstadj;
while(current!=null){
distance[current.adjvex] = current.weight;
current = current.nextadj;
}
for(int i=0;i<numOfVexs;i++){
if(distance[i]==0)
distance[i] = Integer.MAX_VALUE;
}
st[v] = true;
distance[v] = 0;
//开始循环
for(int i=0;i<numOfVexs;i++){
//从未访问顶点中选择路径长度最短的顶点加入访问集合
int min = Integer.MAX_VALUE;
int index = -1;
for(int j=0;j<numOfVexs;j++){
if(!st[j]&&distance[j]<min){
index = j;
min = distance[j];
}
}
if(index!=-1){
st[index] = true;
//找到源点到索引为index顶点的最短路径长度
for(int k=0;k<numOfVexs;k++){
if(!st[k]){
int[] tmp = new int[numOfVexs];
ENode cur = vexs[index].firstadj;
while(cur!=null){
tmp[cur.adjvex] = cur.weight;
cur = cur.nextadj;
}
if(tmp[k]!=0&&distance[k]>min+tmp[k])
distance[k] = min + tmp[k];
}
}
}
}
return distance;
}

说明:在本博客中图的介绍与实现一节中会有该问题详细实现,大家可以参考那个来进行理解。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------