Java写一个迪杰斯特拉算法

迪杰斯特拉算法是一种经典的最短路径算法，其基本思路是从起点开始，逐步扩展到周围的节点，直到到达终点为止。这里给出Java实现：

import java.util.*;

public class DijkstraAlgorithm {

    private static final int INF = Integer.MAX_VALUE; // 表示两点之间没有边相连

    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length; // 图的大小
        boolean[] visited = new boolean[n]; // 记录每个节点是否已经访问过
        int[] dist = new int[n]; // 记录起点到每个节点的距离

        Arrays.fill(dist, INF); // 初始化距离为无穷大
        dist[start] = 0; // 起点到自身的距离为0

        for (int i = 0; i < n - 1; i++) { // 执行n-1次循环
            int u = findMinDist(dist, visited); // 找到当前未访问节点中距离最近的节点
            visited[u] = true; // 标记节点u为已访问

            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != INF && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                    // 如果节点v未访问过、节点u与v之间有边相连、起点到节点u的距离不为无穷大、
                    // 且起点到节点v的距离大于起点到节点u的距离加上节点u到节点v的距离
                    dist[v] = dist[u] + graph[u][v]; // 更新起点到节点v的距离
                }
            }
        }

        // 输出起点到各节点的最短距离
        System.out.println("起点到各节点的最短距离：");
        for (int i = 0; i < n; i++) {
            System.out.println(start + " -> " + i + "：" + dist[i]);
        }
    }

    private static int findMinDist(int[] dist, boolean[] visited) {
        int minDist = INF;
        int minIndex = -1;

        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, INF, 1, 4},
                {2, 0, 4, 3, INF},
                {INF, 4, 0, 8, INF},
                {1, 3, 8, 0, 5},
                {4, INF, INF, 5, 0}
        };
        dijkstra(graph, 0);
    }
}

这里以一个带权重的无向图为例，图的表示方式是一个二维数组，其中每个元素表示两点之间的距离，INF表示两点之间没有边相连。在实现中，用dist数组记录起点到每个节点的距离，visited数组记录每个节点是否已经访问过。在每次循环中，找到当前未访问节点中距离最近的节点u，并标记节点u为已访问，然后遍历节点u周围的节点v，如果节点v未访问过、节点u与v之间有边相连、起点到节点u的距离不为无穷大、且起点到节点v的距离大于起点到节点u的距离加上节点u到节点v的距离，则更新起点到节点v的距离。最后输出起点到各节点的最短距离。