Java实现Dijkstra算法的示例代码

让我来为你详细讲解“Java实现Dijkstra算法的示例代码”的完整攻略。

什么是Dijkstra算法？

Dijkstra算法是一种用于在加权图中查找最短路径的算法。其基本思路是从起点开始，依次考虑所有可能的路径，并选择当前距离最近的节点作为下一个起点。通过不断更新节点的最短距离，最终找到起点到终点的最短路径。

实现步骤

实现Dijkstra算法的步骤如下：

初始化：将起点的距离设置为0，其他节点的距离设置为无穷大；
选择当前距离最近的节点作为下一个起点；
遍历该节点的所有邻居节点，更新它们的最短距离；
标记该节点为已访问，重复步骤2-4，直到访问完所有节点。

Java示例代码

下面是一个简单的Java实现Dijkstra算法的示例代码：

import java.util.*;

public class DijkstraAlgorithm {

    public static void main(String[] args) {
        // 1. 构建图
        int[][] adjacencyMatrix = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                   {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                   {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                   {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                   {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                   {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                   {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                   {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                   {0, 0, 2, 0, 0, 0, 6, 7, 0}};
        int size = adjacencyMatrix.length;

        // 2. 初始化距离和访问状态
        int[] distances = new int[size];
        boolean[] visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            distances[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        // 3. 计算最短路径
        distances[0] = 0;
        for (int i = 0; i < size - 1; i++) {
            // 选取当前距离最近的节点
            int minDistance = Integer.MAX_VALUE;
            int current = -1;
            for (int j = 0; j < size; j++) {
                if (!visited[j] && distances[j] < minDistance) {
                    current = j;
                    minDistance = distances[j];
                }
            }

            // 更新邻居节点的最短距离
            visited[current] = true;
            for (int j = 0; j < size; j++) {
                if (adjacencyMatrix[current][j] > 0) {
                    int distance = distances[current] + adjacencyMatrix[current][j];
                    if (distance < distances[j]) {
                        distances[j] = distance;
                    }
                }
            }
        }

        // 4. 输出最短距离
        for (int i = 0; i < size; i++) {
            System.out.printf("Distance from node %d to node 0 is %d\n", i, distances[i]);
        }
    }
}

这个示例代码有以下两个说明：

示例1：

示例1中的邻接矩阵表示如下图所示的加权有向图：

 4     8

(0)--->(1)--->(2)
/| | |\
8 | |7 |2
| | |/
(7)<---(6)<---(5)
1 |
|
\/
(4)---9-->(3)

执行这段代码后，输出如下：

Distance from node 0 to node 0 is 0
Distance from node 1 to node 0 is 4
Distance from node 2 to node 0 is 12
Distance from node 3 to node 0 is 19
Distance from node 4 to node 0 is 21
Distance from node 5 to node 0 is 11
Distance from node 6 to node 0 is 9
Distance from node 7 to node 0 is 8
Distance from node 8 to node 0 is 14

结果表明从起点0到其他节点的最短距离分别是0, 4, 12, 19, 21, 11, 9, 8和14。

示例2：

在示例1的邻接矩阵中，将(4,3)的权重设置为0，则表示有个节点可以直接到达，从而改变了最短距离的计算。修改后的邻接矩阵表示如下：

 4     8

(0)--->(1)--->(2)
/| | |\
8 | |7 |2
| | |/
(7)<---(6)<---(5)
1 |
9
|
\/
(3)

修改后的代码如下：

import java.util.*;

public class DijkstraAlgorithm {

    public static void main(String[] args) {
        // 1. 构建图
        int[][] adjacencyMatrix = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                   {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                   {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                   {0, 0, 7, 0, 0, 14, 0, 0, 0},
                                   {0, 0, 0, 0, 0, 10, 0, 0, 0},
                                   {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                   {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                   {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                   {0, 0, 2, 0, 0, 0, 6, 7, 0}};
        int size = adjacencyMatrix.length;

        // 2. 初始化距离和访问状态
        int[] distances = new int[size];
        boolean[] visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            distances[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        // 3. 计算最短路径
        distances[0] = 0;
        for (int i = 0; i < size - 1; i++) {
            // 选取当前距离最近的节点
            int minDistance = Integer.MAX_VALUE;
            int current = -1;
            for (int j = 0; j < size; j++) {
                if (!visited[j] && distances[j] < minDistance) {
                    current = j;
                    minDistance = distances[j];
                }
            }

            // 更新邻居节点的最短距离
            visited[current] = true;
            for (int j = 0; j < size; j++) {
                if (adjacencyMatrix[current][j] > 0) {
                    int distance = distances[current] + adjacencyMatrix[current][j];
                    if (distance < distances[j]) {
                        distances[j] = distance;
                    }
                }
            }
        }

        // 4. 输出最短距离
        for (int i = 0; i < size; i++) {
            System.out.printf("Distance from node %d to node 0 is %d\n", i, distances[i]);
        }
    }
}