java实现Dijkstra最短路径算法

下面是“java实现Dijkstra最短路径算法”的详细攻略：

什么是Dijkstra最短路径算法

Dijkstra最短路径算法是一种基于图的贪心算法，用于求解从一个出发点到其它节点的最短路径。算法适用于有向或无向加权图。

算法思路

1. 初始化，将起点到各个节点的距离全部初始化为无穷大，将起点到自己的距离设置为0。
2. 选取起点，将其设置为当前未处理节点中距离起点最短的节点。
3. 以选取的节点为中心点，更新所有与之相邻的节点的距离。具体方法是将中心点到起点的距离加上中心点到相邻节点的距离，如果大于相邻节点当前距离，则将其距离更新为目前计算得到的更小值。
4. 将当前节点标记为已处理的节点，当所有节点都被标记后，算法结束。

Java实现

import java.util.*;

public class DijkstraAlgorithm {
    private int numOfVertices;
    private int[] distance;
    private boolean[] visited;
    private int[][] adjacencyMatrix;

    public DijkstraAlgorithm(int numOfVertices) {
        this.numOfVertices = numOfVertices;
        distance = new int[numOfVertices];
        visited = new boolean[numOfVertices];
        adjacencyMatrix = new int[numOfVertices][numOfVertices];
    }

    public void dijkstra(int[][] graph, int source) {
        // 初始化distance数组
        for (int i = 0; i < numOfVertices; i++) {
            distance[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        // 起点到起点的距离为0
        distance[source] = 0;

        for (int i = 1; i < numOfVertices; i++) {
            // 选取距离最小并且未被访问过的节点
            int u = getMinDistanceVertex(distance, visited);

            visited[u] = true;

            for (int v = 0; v < numOfVertices; v++) {
                if (graph[u][v] != 0 && !visited[v] && distance[u] != Integer.MAX_VALUE &&
                        distance[u] + graph[u][v] < distance[v]) {
                    distance[v] = distance[u] + graph[u][v];
                }
            }
        }

        // 输出到每个节点的最短距离
        for (int i = 0; i < distance.length; i++) {
            System.out.println("从源节点到" + i + "的最短距离是：" + distance[i]);
        }
    }

    private int getMinDistanceVertex(int[] distance, boolean[] visited) {
        int minDistanceVertex = -1;
        for (int i = 0; i < numOfVertices; i++) {
            if (!visited[i] && (minDistanceVertex == -1 || distance[i] < distance[minDistanceVertex])) {
                minDistanceVertex = i;
            }
        }
        return minDistanceVertex;
    }

    // 示例
    public static void main(String[] args) {
        int[][] graph1 = {{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[][] graph2 = {{0, 10, 15, 5},
                          {0, 0, 0, 20},
                          {0, 0, 0, 0},
                          {0, 0, 0, 0}};

        DijkstraAlgorithm dijkstra1 = new DijkstraAlgorithm(graph1.length);
        DijkstraAlgorithm dijkstra2 = new DijkstraAlgorithm(graph2.length);

        dijkstra1.dijkstra(graph1, 0);
        dijkstra2.dijkstra(graph2, 0);
    }
}

以上代码中，我们首先定义了四个成员变量：numOfVertices表示节点数量，distance表示源节点到各个节点的距离，visited表示该节点是否被处理过，adjacencyMatrix表示各个节点之间的距离矩阵。

然后定义了DijkstraAlgorithm类的构造函数，用于初始化成员变量。

接着实现了dijkstra方法，其中需要明确处理流程，具体有上面算法步骤中所述。

最后我们定义了两个示例图，分别为graph1和graph2，其中graph1是经典的测试用例，用于测试该算法的正确性；graph2是一个较小的图例，用于示范输入矩阵的格式。

运行结果如下：

从源节点到0的最短距离是：0
从源节点到1的最短距离是：4
从源节点到2的最短距离是：12
从源节点到3的最短距离是：19
从源节点到4的最短距离是：21
从源节点到5的最短距离是：11
从源节点到6的最短距离是：9
从源节点到7的最短距离是：8
从源节点到8的最短距离是：14

从源节点到0的最短距离是：0
从源节点到1的最短距离是：10
从源节点到2的最短距离是：15
从源节点到3的最短距离是：5

从结果中可以看出，Dijkstra算法的实现是正确的，而且输出结果也符合预期。

总的来说，Dijkstra最短路径算法是一个常用的图论算法，非常适合求解从一个出发点到其它节点的最短路径问题。以上就是Java实现Dijkstra最短路径算法的全部攻略，希望对你有所帮助。