Dijkstra算法实现

1. 算法简介

  • 迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
  • 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。
  • 引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
  • 初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是”起点s到该顶点的路径”。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 … 重复该操作,直到遍历完所有顶点。

2. 算法图解

  • 选定A节点初始化,如下图所示:

  • 找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( ‘D 到 B,C,E 的距离’ + ‘AD 距离’ < ‘A 到 B,C,E 的距离’ )来更新U集合:

  • 这时候 A->B, A->C都为3,没关系。其实这时候他俩都是最短距离,如果从算法逻辑来讲的话,会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' )如图所示,这时候A->B距离 其实为 A->D->B

  • 思路就是这样,往后就是大同小异了:

  • 算法结束:

3. 代码实现

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
public class Dijkstra {
public static final int M = 100000; // 代表正无穷

/**
*
* @param start 起点的编号start
* @param weight 有向图的权重矩阵
* @return start到每个点的最短路径
*/
public static int[] dij(int start, int[][] weight){
int n = weight.length;
int distance[] = new int[n];//保存start点到其他点的最短距离
String path[] = new String[n];//保存start到其他点的最短路径字符串信息
for (int i = 0; i < n; i++)
path[i] = new String(start + "-->" + i);
int visited[] = new int[n];//标记该点是否已求出,1表示求出

//初始化,第一个点已经求出
distance[start] = 0;
visited[start] = 1;

// 求start到其余n-1个点
for(int i=1; i<n; i++){
int k =-1; //存放一个距离start最近的未标记顶点
int min = 10000;
for(int j=0; j<n; j++){
if(visited[j]==0 && weight[start][j]<min){
min = weight[start][j];
k = j;
}
}
// 已求得start到第k个点,标记并保存距离
distance[k] = min;
visited[k] = 1;
// 根据之前求的k点更新start到其余点的距离
for(int j=0; j<n; j++){
if(visited[j]==0 && weight[start][k]+weight[k][j]<weight[start][j]){
weight[start][j] = weight[start][k]+weight[k][j];
path[j] = path[k]+"-->"+j;
}
}
}
for (int i = 0; i < n; i++) {

System.out.println("从" + start + "出发到" + i + "的最短路径为:" + path[i]);
}
System.out.println("=====================================");
return distance;

}

public static void main(String[] args) {
// 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
// 点到自身距离为0, M为正无穷
int[][] weight1 = {
{0,4,M,2,M},
{4,0,4,1,M},
{M,4,0,1,3},
{2,1,1,0,7},
{M,M,3,7,0}
};

int start = 0;

int[] shortPath = dij(start, weight1);

for (int i = 0; i < shortPath.length; i++)
System.out.println("从" + start + "出发到" + i + "的最短距离为:" + shortPath[i]);
}
}
-------------The End-------------
谢谢大锅请我喝杯阔乐~