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

(三)寻找图的最短路径

最短路径

最短路径问题可以根据图是否为加权图来区分为两种大问题:段数最少的最短路径权值之和最小的最短路径。

段数最少的最短路径

这种较为简单,使用广度优先搜索即可。类似于树的层次遍历,需要借助于队列来实现。

在遍历的过程中,对于已经检查过的点,应该标记为已检查,且不再检查它,否则可能会导致无限循环。可以使用另外一个列表存放已经检查过的结点,找到即为到达,第一次找到,即为跳转最少。如果到最后队列为空,表明没有路径可以到达。

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
49
50
51
52
53
54
55
public int[] dijkstra(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
//S,T集合用一个数组来进行表示 true表示S,false表示T
boolean[] st = new boolean[numOfVexs];
int[] distance = new int[numOfVexs];
//初始化
ENode current = vexs[v].firstadj;
//查询邻接表,记录与v号结点相邻的结点的距离
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;
}
//单独处理v号结点 ,将其加入集合S,并且自身到自身的距离为0
st[v] = true;
distance[v] = 0;
//初始化结束,开始处理
for(int i=0;i<numOfVexs;i++){
//从distance数组中找出最小值
int index = -1; //存储最小值下标
int min = Integer.MAX_VALUE; //存储最小值
for(int j=0;j<distance.length;j++){
//从集合T中寻找最小值
if(!st[j]&&distance[j]<min){
index = j;
min = distance[index];
}
}
//找到最小值后
if(index!=-1){
//将最小值放入集合S中
st[index] = true;
//临时数组用于存放当前结点到各个节点的距离
int[] tmp = new int[numOfVexs];
current = vexs[index].firstadj;
//循环查找当前节点与所有节点的距离 0按照无穷大处理
while(current!=null){
tmp[current.adjvex] = current.weight;
current = current.nextadj;
}
for(int j=0;j<distance.length;j++){
if(!st[j]&&tmp[j]!=0&&distance[j]>tmp[j]+min){
distance[j] = tmp[j] + min;
}
}
}
}
return distance;
}

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

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