java实现迪杰斯特拉

迪杰斯特拉算法是一种经典的最短路径算法，主要用于解决带权图中的单源最短路径问题。下面是Java实现迪杰斯特拉算法的示例代码：

import java.util.Arrays;

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

    /**
     * 计算从源点出发到各个顶点的最短距离
     * @param graph 图
     * @param src 源点
     * @return 最短距离数组
     */
    public static int[] dijkstra(int[][] graph, int src) {
        int n = graph.length; // 图中顶点的个数
        int[] dist = new int[n]; // 记录从源点到各个顶点的最短距离
        boolean[] visited = new boolean[n]; // 标记顶点是否被访问过
        Arrays.fill(dist, INF); // 初始化为无穷大
        dist[src] = 0; // 到自己的距离为0

        for (int i = 0; i < n - 1; i++) {
            int u = findMinDist(dist, visited); // 找到未访问过的距离最短的顶点
            visited[u] = true; // 标记为已访问
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                    // 如果v未被访问过，且u和v之间有边相连，且通过u可以使得src到v的距离更短
                    dist[v] = dist[u] + graph[u][v]; // 更新距离
                }
            }
        }
        return dist;
    }

    /**
     * 找到未访问过的距离最短的顶点
     * @param dist 记录从源点到各个顶点的最短距离
     * @param visited 标记顶点是否被访问过
     * @return 未访问过的距离最短的顶点
     */
    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 = {
                {INF, 2, 4, INF, INF},
                {INF, INF, 1, 7, INF},
                {INF, INF, INF, INF, 3},
                {INF, INF, INF, INF, 1},
                {INF, INF, INF, INF, INF}
        };

        int[] dist = dijkstra(graph, 0);
        System.out.println(Arrays.toString(dist)); // [0, 2, 4, 9, 7]
    }
}

在上面的示例代码中，我们使用了一个二维数组`graph`来表示图，其中`graph[i][j]`表示从顶点i到顶点j的边的权值。如果两个顶点之间没有边相连，则将`graph[i][j]`设置为一个足够大的值，这里我们使用`Integer.MAX_VALUE`表示。在`dijkstra`方法中，我们首先初始化从源点到各个顶点的距离为无穷大，然后从源点开始，每次找到未访问过的距离最短的顶点，标记为已访问，并更新与该顶点相邻的顶点的距离。最终得到从源点出发到各个顶点的最短距离。