Dijkstra算法原理及其实现
参考书籍：《算法（第4版）》
$Dijkstra$ 算法应用于带权有向图中求最短路径问题。通俗来讲就是不断选择权值最小的边加入集合直到所有顶点都在集合中，属于贪心算法。需要注意的是，$Dijkstra$ 算法只能用于解决边权非负的图类问题。
假设对于一个带权有向图 $G(V,E)$ 以邻接矩阵表示，其所有边存储在一个二维整型数组 $matrix[\ \ ][\ \ ]$ 中， $matrix[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 之间的边，值为边的权值，若值为 $∞$ ，说明该边不存在。为了实现 $Dijkstra$ 算法，我们需要一个布尔值数组 $visit[\ \ ]$ ，用于判断顶点是否访问过，或者说是否在集合中；一个整型数组 $distance[\ \ ]$ 用于储存原点到每个点的最短距离。定义了基本的结构，就可以实现算法了，步骤为：
- 从 $V$ 中选择一个点 $s$ 作为原点，将邻接矩阵中的 $matrix[s]$ 数组复制到 $distance[s]$ （复制后 $distance[s]$ 应为 $0$ ），建立一个 $visit[\ \ ]$ 数组并清零。
- 从 $V$ 中选择一个顶点 $u$ 加入集合，其中点 $u$ 满足：
- 之前未曾访问过点 $u$ （即 $visit[u] = false$ ）。
- 与 $s$ 距离最短（即 $distance[u]$ 的值最小）。
- 以 $u$ 为中心点，对于每个与 $u$ 相邻的顶点 $k$ ，令 $distance[k] = Min(distance[k], distance[u] + matrix[u][k])$ ，这一步也称为
松弛( $relaxation$ )。 - 重复2、3直到所有顶点加入集合。
$Dijkstra$ 算法类似于 $Prim$ 算法，实质上都是构造了一颗树。经过以上步骤之后，我们得到了一个 $distance[\ \ ]$ 数组，其中的值为从原点 $s$ 到图中其他所有点的最短距离。在使用代码实现的过程中，有些情况下我们可以使用优先队列来简化寻找最小权值的这一过程。如果我们确认了一幅图是无环图，那么我们也可以不使用 $visit[\ \ ]$ ，而是通过拓扑排序的顺序依次遍历顶点。
将上述过程转化为代码如下：
public class Dijkstra {
public int[] dijkstra (int s, int[][] matrix) {
int length = matrix.length;
bool[] visit = new boolean[length];
int[] distance = new int[length];
System.arraycopy(matrix[s], 0, distance, 0, length); // 复制邻接矩阵的值
distance[s] = 0;
visit[s] = true;
// 遍历其他顶点
for (int i = 1; i < length; i++) {
int min = Integer.MAX_VALUE;
int u = s;
// 寻找最小权值
for (int j = 0; j < n; j++)
if (!visit[j] && distance[j] < min) {
min = distance[j];
u = j;
}
visit[u] = true;
// 松弛
for (int k = 0; k < n; k++)
if (!visit[k] && distance[k] > distance[u] + matrix[u][k])
distance[k] = distance[u] + matrix[u][k];
}
return distance;
}
}
至此我们实现了 $Dijkstra$ 算法。虽然这里我们没有使用优先队列，但是使用优先队列是可行的，也可以在一定程度上加快速度。 $Dijkstra$ 算法有许多种优化策略，而不同的策略对应的时间复杂度也是不同，因此在此不作过多叙述，如果感兴趣的话可以在 Dijkstra’s algorithm - Wikipedia 中查看。如果我们将寻找最小权值的过程改为寻找最大权值，那么就可以由最短路径算法改为最长路径算法。
关于 $Dijkstra$ 算法有很多题，在这里举一道题为例。
显然在这道题就是一道求最短距离的算法，分别以每个城市为原点计算 $distance[\ \ ]$ 数组，再遍历数组得到答案，最终输出最大值即可。我们直接将上面的 $Dijkstra$ 算法的模板套进去就行了。
class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
// 将边集转换为邻接矩阵
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) matrix[i][j] = Integer.MAX_VALUE; // 用最大值代表无穷
for (int[] edge : edges) matrix[edge[0]][edge[1]] = matrix[edge[1]][edge[0]] = edge[2];
int res = 0, MIN = n + 1;
// 分别以每个点为原点，调用 Dijkstra算法
for (int i = 0; i < n; i++) {
int[] distance = new int[n];
boolean[] visit = new boolean[n];
System.arraycopy(matrix[i], 0, distance, 0, n);
distance[i] = 0;
visit[i] = true;
for (int j = 1; j < n; j++) {
int min = Integer.MAX_VALUE;
int u = i;
for (int k = 0; k < n; k++)
if (!visit[k] && distance[k] < min) {
min = distance[k];
u = k;
}
visit[u] = true;
for (int k = 0; k < n; k++)
if (!visit[k] && distance[k] > distance[u] + matrix[u][k])
distance[k] = distance[u] + matrix[u][k];
}
// 计算相邻城市数
int count = 0;
for (int dist : distance)
if (dist <= distanceThreshold) count++;
if (count <= MIN) {
MIN = count;
res = i;
}
}
return res;
}
}