迪杰斯特拉算法

应用场景-最短路径问题

战争时期，胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从G点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄

各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里

问：如何计算出G村庄到 其它各个村庄的最短距离?

如果从其它点出发到各个点的最短距离又是多少?

迪杰斯特拉算法基本介绍

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

基本思想：

  1. 引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
  2. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，如果s和v不相邻，则v的距离为∞]。
  3. 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
  4. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
  5. 重复步骤(3)和(4)，直到遍历完所有顶点。

图解思路如下：

以上图为例，来对迪杰斯特拉进行算法演示(以第4个顶点D为起点)。

最短路径问题的代码实现

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
package com.nanzx.dijkstra;

import java.util.Arrays;

public class DijkstraAlgorithm {

	public static void main(String[] args) {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		// 邻接矩阵
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;// 表示不可以连接
		matrix[0] = new int[] { N, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, N, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, N, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, N, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, N, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, N, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, N };

		Graph graph = new Graph(vertex, matrix);
		Dijkstra djs = new Dijkstra(graph, 6);
		djs.dijkstra();
		djs.show();
	}
}

class Graph {
	public char[] vertex; // 顶点数组
	public int[][] matrix; // 邻接矩阵

	// 构造器
	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}

	// 显示图
	public void showGraph() {
		for (int[] link : matrix) {
			System.out.println(Arrays.toString(link));
		}
	}
}

class Dijkstra {
	private int startVertex;// 源点，即计算"源点startVertex"到其它顶点的最短路径
	private Graph graph;// 图
	private int[] visited;// 记录各个顶点是否访问过，1表示访问过，0未访问
	private int[] prev;// prev[i]的值是"顶点startVertex"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点
	private int[] dist;// dist[i]是"顶点startVertex"到"顶点i"的最短路径的长度。

	// 初始化构造器
	public Dijkstra(Graph graph, int startVertex) {
		this.startVertex = startVertex;
		this.graph = graph;
		this.visited = new int[graph.vertex.length];
		this.prev = new int[graph.vertex.length];
		this.dist = new int[graph.vertex.length];

		visited[startVertex] = 1;// 标记源点已被访问

		Arrays.fill(dist, 65535);
		for (int i = 0; i < graph.matrix[startVertex].length; i++) {// 初始化源点到各顶点距离
			if (graph.matrix[startVertex][i] < dist[i]) {
				dist[i] = graph.matrix[startVertex][i];
			}
		}
		dist[startVertex] = 0;// 标记源点到自己的距离为0

		for (int i = 0; i < prev.length; i++) {// 将其他顶点的前驱顶点都指向源点
			if (i != startVertex) {
				prev[i] = startVertex;
			}
		}
		prev[startVertex] = -1;//源点的前驱顶点为-1
	}

	// 核心算法
	public void dijkstra() {
		for (int n = 0; n < graph.vertex.length - 1; n++) {// 有n-1个需要计算顶点到源点距离
			int min = 0;
			int minDist = 65535;
			for (int i = 0; i < dist.length; i++) {// 找到距离最短的顶点
				if (dist[i] < minDist && dist[i] != 0 && visited[i] != 1) {
					min = i;
					minDist = dist[min];
				}
			}
			visited[min] = 1;// 标记该顶点为已访问
			for (int i = 0; i < graph.matrix[min].length; i++) {// 更新其它顶点的距离
				if (graph.matrix[min][i] + dist[min] < dist[i] && visited[i] == 0) {
					dist[i] = graph.matrix[min][i] + dist[min];
					prev[i] = min;
				}
			}
		}
	}

	// 输出结果
	public void show() {

		System.out.print("visited数组：");
		for (int i : visited) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.print("prev数组：");
		for (int i : prev) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.print("dist数组：");
		for (int i : dist) {
			System.out.print(i + " ");
		}
		System.out.println();

		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		System.out.print(vertex[startVertex] + " 到各个顶点的最短距离：");
		int count = 0;
		for (int i : dist) {
			if (i != 65535) {
				System.out.print(vertex[count] + "(" + i + ") ");
			} else {
				System.out.println(vertex[count] + "(N) ");
			}
			count++;
		}
	}
}

运行结果：

visited数组：1 1 1 1 1 1 1
prev数组：6 6 0 5 6 6 -1
dist数组：2 3 9 10 4 6 0
G 到各个顶点的最短距离：A(2) B(3) C(9) D(10) E(4) F(6) G(0)