java迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于解决带权图中最短路径问题的算法。它以起始点为中心，逐层向外扩展，直到扩展到终点为止。以下是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; // 图的顶点数

        int[] dist = new int[n]; // 存储起始点到各个顶点的最短距离
        boolean[] visited = new boolean[n]; // 记录顶点是否已被访问

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

        for (int i = 0; i < n - 1; i++) {
            int minDist = INF;
            int minIndex = -1;

            // 找到当前未访问的顶点中距离起始点最近的顶点
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIndex = j;
                }
            }

            if (minIndex == -1) {
                break; // 所有顶点都已访问过，退出循环
            }

            visited[minIndex] = true; // 标记该顶点为已访问

            // 更新与当前顶点相邻的顶点的最短距离
            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[minIndex][j] != INF && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                    dist[j] = dist[minIndex] + graph[minIndex][j];
                }
            }
        }

        // 输出起始点到各个顶点的最短距离
        for (int i = 0; i < n; i++) {
            System.out.println("从起始点到顶点 " + i + " 的最短距离为：" + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 4, INF, INF},
                {2, 0, 1, 4, 2},
                {4, 1, 0, 1, 3},
                {INF, 4, 1, 0, 1},
                {INF, 2, 3, 1, 0}
        };
        int start = 0; // 起始点的索引

        dijkstra(graph, start);
    }
}

这段代码实现了迪杰斯特拉算法，通过传入一个带权图的邻接矩阵和起始点的索引，计算出起始点到各个顶点的最短距离，并输出结果。