最短路径算法 java

以下是使用Java实现的最短路径算法（Dijkstra算法）的示例代码：

import java.util.Arrays;

public class DijkstraAlgorithm {
    private static final int INF = Integer.MAX_VALUE; // 无穷大

    public void dijkstra(int[][] graph, int start) {
        int n = graph.length; // 图的顶点数

        // 创建一个数组dist来保存从起始顶点到其他顶点的最短距离
        int[] dist = new int[n];
        Arrays.fill(dist, INF); // 初始化为无穷大
        dist[start] = 0; // 起始顶点到自身的距离为0

        // 创建一个数组visited来标记顶点是否已被访问过
        boolean[] visited = new boolean[n];

        // 循环n次，每次找出一个顶点的最短路径
        for (int i = 0; i < n; 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;
                }
            }

            // 标记该顶点为已访问
            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("从顶点 " + start + " 到顶点 " + i + " 的最短距离为：" + dist[i]);
        }
    }

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

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