最短路径 Dijkstra 算法（迪杰斯特拉算法）
最短路径 Dijkstra 算法（迪杰斯特拉算法）
算法原理
Dijkstra 算法用于计算一个节点（源节点）到其他所有节点的最短路径。它的基本思想是贪心算法，每次选择距离源节点最近的未确定最短路径的节点，将其标记为已确定最短路径的节点，然后更新与该节点相邻的节点的距离。例如，假设有一个交通网络图，节点代表城市，边代表城市之间的道路，边的权重代表道路的长度。Dijkstra 算法可以帮助我们找到从一个城市（源节点）到其他所有城市的最短路径。
代码实现步骤
步骤一：初始化数据结构
需要一个数组来存储从源节点到各个节点的最短距离，初始时，源节点到自身的距离为 0，到其他节点的距离可以设为一个很大的值（表示无穷大）。同时，需要一个布尔数组来标记哪些节点已经确定了最短路径。
int[] dist = new int[numVertices];
boolean[] visited = new boolean[numVertices];
for (int i = 0; i < numVertices; i++) {
dist[i] = Integer.MAX_VALUE;
visited[i] = false;
}
dist[source] = 0;步骤二：循环选择节点并更新距离
在每次循环中，找到未访问节点中距离源节点最近的节点。然后，对于该节点的所有邻居节点，更新它们到源节点的距离。
for (int count = 0; count < numVertices - 1; count++) {
int u = findMinDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < numVertices; v++) {
if (!visited[v] && graph[u][v]!= 0 && dist[u]!= Integer.MAX_VALUE && dist[u]+graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}步骤三：方法findMinDistance实现
这个方法用于找到未访问节点中距离源节点最近的节点。
private int findMinDistance(int[] dist, boolean[] visited) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < numVertices; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}完整实例
import java.util.Arrays;
public class Demo6 {
// 表示图中节点的数量
private static final int V;
// 存储图的邻接矩阵，graph[i][j]表示从节点i到节点j的边的权重，若不存在边则为0
private static int[][] graph;
static {
V = 6;
graph = new int[][]{
{0, 2, 0, 1, 0, 0},
{0, 0, 4, 0, 1, 0},
{0, 0, 0, 0, 0, 2},
{0, 0, 0, 0, 3, 0},
{0, 0, 0, 0, 0, 2},
{0, 0, 0, 0, 0, 0}
};
}
// 找到未访问节点中距离源节点最近的节点
private static int minDistance(int[] dist, boolean[] sptSet) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < V; v++) {
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
// 迪杰斯特拉算法的核心实现方法
private static void dijkstra(int src) {
// dist数组存储从源节点到各个节点的最短距离，初始化为最大值（表示无穷大）
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// sptSet数组用于标记节点是否已经确定了最短路径，初始化为false
boolean[] sptSet = new boolean[V];
// 循环V - 1次，每次确定一个节点的最短路径
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
// 更新与当前确定的节点u相邻的节点的距离
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 输出从源节点到各个节点的最短距离
printSolution(dist);
}
private static void printSolution(int[] dist) {
System.out.println("从源节点到各个节点的最短距离如下：");
for (int i = 0; i < V; i++) {
System.out.println("节点 " + i + " 的最短距离：" + dist[i]);
}
}
public static void main(String[] args) {
int source = 0;
dijkstra(source);
}
}以下是对上述代码的详细解释： 类和变量定义部分： DijkstraAlgorithm 类用于封装迪杰斯特拉算法相关的方法和数据。 V 变量表示图中节点的总数，这里通过静态代码块初始化设置为 6。 graph 二维数组用于表示图的邻接矩阵，同样在静态代码块中进行初始化，其中 graph[i][j] 的值代表从节点 i 到节点 j 的边的权重，如果没有边相连则权重为 0。 minDistance 方法： 该方法的作用是在还未确定最短路径的节点（即 sptSet 数组中对应元素为 false 的节点）中，找出距离源节点最近的那个节点。 它通过遍历所有节点，比较距离值（存储在 dist 数组中）并结合 sptSet 数组来判断节点是否已处理过，最终返回距离最小的节点的索引。 dijkstra 方法： 这是迪杰斯特拉算法的核心实现部分。 首先，初始化 dist 数组，将所有元素设置为 Integer.MAX_VALUE（表示无穷大），然后将源节点到自身的距离设为 0。同时，初始化 sptSet 数组，所有元素初始化为 false，用于标记节点是否已经确定了最短路径。 接着，通过一个循环（循环次数为 V - 1），每次先调用 minDistance 方法找到当前未确定最短路径的节点中距离源节点最近的节点 u，将其标记为已确定最短路径（即 sptSet[u] 设置为 true）。 然后，遍历所有节点 v，对于那些未确定最短路径（sptSet[v] 为 false）且与节点 u 有边相连（graph[u][v] 不为 0），并且经过节点 u 到节点 v 的距离比当前记录的 dist[v] 更小的情况，更新 dist[v] 的值为经过节点 u 后的新距离（dist[u] + graph[u][v]）。 最后，调用 printSolution 方法输出从源节点到各个节点的最短距离。 printSolution 方法： 简单地遍历 dist 数组，将每个节点对应的最短距离输出到控制台，格式为 “节点 i 的最短距离：dist[i]”。 main 方法： 在 main 方法中，指定源节点的索引（这里设置为 0），然后调用 dijkstra 方法来执行迪杰斯特拉算法，计算并输出从该源节点到其他所有节点的最短距离。
腾讯云开发者
