最短路径算法之Dijkstra算法(java实现)

Dijkstra算法是一种常用的最短路径算法，它可以用于计算从源节点到所有其他节点的最短路径。下面是它的Java实现：

import java.util.*;

public class DijkstraAlgorithm {
    private int V; // 节点数
    private int[][] graph; // 图
    private boolean[] visited; // 标记节点是否访问过
    private int[] dist; // 存储源节点到各个节点的最短距离

    public DijkstraAlgorithm(int[][] graph) {
        this.V = graph.length;
        this.graph = graph;
        this.visited = new boolean[V];
        this.dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化源节点到各个节点的距离为无穷大
    }

    // 找到未访问节点中距离源节点最近的节点
    private int findMinDistNode() {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    public void dijkstra(int src) {
        dist[src] = 0;

        for (int i = 0; i < V - 1; i++) {
            int u = findMinDistNode();
            visited[u] = true;

            for (int v = 0; v < V; 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];
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = new int[][] { { 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 } };

        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
        dijkstra.dijkstra(0);

        System.out.println("从源节点0到其他节点的最短距离为:");
        for (int i = 0; i < graph.length; i++) {
            System.out.println(i + ": " + dijkstra.dist[i]);
        }
    }
}

这个实现中，我们用一个二维数组来表示图，其中元素graph[i][j]表示从节点i到节点j的距离；用一个boolean类型的数组visited来标记节点是否已经被访问过；用一个一维数组dist来存储源节点到各个节点的最短距离。在实现中，我们首先将源节点到各个节点的距离初始化为无穷大，然后以源节点为起点开始遍历，每次找到未访问节点中距离源节点最近的节点，将其标记为已访问，然后更新其邻居节点的距离。重复以上步骤，直到所有节点都被访问过为止。最后，我们输出源节点到各个节点的最短距离即可。

以上就是Dijkstra算法的Java实现，希望对你有帮助！