java实现迪杰斯特拉算法并输出经过元素的下标

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于图形的贪心算法，用于计算一个节点到其他所有节点的最短路径。

以下是 Java 实现迪杰斯特拉算法并输出经过元素的下标的示例代码：

import java.util.Arrays;

public class Dijkstra {
    private static final int MAX = Integer.MAX_VALUE;

    public static void shortestPath(int[][] graph, int start) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        int[][] paths = new int[n][n];
        Arrays.fill(dist, MAX);
        dist[start] = 0;

        for (int i = 0; i < n; i++) {
            int min = findMin(dist, visited);
            visited[min] = true;

            for (int j = 0; j < n; j++) {
                if (graph[min][j] != 0 && !visited[j] && dist[min] != MAX && dist[min] + graph[min][j] < dist[j]) {
                    dist[j] = dist[min] + graph[min][j];
                    paths[j] = Arrays.copyOf(paths[min], n);
                    paths[j][j] = j;
                }
            }
        }

        System.out.println("Shortest paths from vertex " + start + ":");
        for (int i = 0; i < n; i++) {
            if (i != start) {
                System.out.print(start + "->" + i + ": " + dist[i] + ", path: [");
                int[] path = paths[i];
                for (int j = 0; j < n; j++) {
                    if (path[j] != 0) {
                        System.out.print(path[j] + " ");
                    }
                }
                System.out.println(i + "]");
            }
        }
    }

    private static int findMin(int[] dist, boolean[] visited) {
        int min = MAX;
        int index = -1;

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

        return index;
    }

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

        shortestPath(graph, 0);
    }
}

在上面的代码中，我们定义了一个 `shortestPath` 方法来计算最短路径。该方法使用一个二维数组 `graph` 来表示图形，其中 `graph[i][j]` 表示从节点 i 到节点 j 的距离。我们还定义了一个 `visited` 数组来表示哪些节点已经被访问过，以及一个 `dist` 数组来存储从起始节点到每个节点的距离。我们还定义了一个 `paths` 二维数组，用于存储从起始节点到每个节点的路径。

在 `shortestPath` 方法中，我们首先初始化 `visited` 和 `dist` 数组。然后，我们开始遍历所有节点。每次迭代，我们选择一个距离起始节点最近的未访问节点。然后，我们遍历与该节点相邻的节点，计算从起始节点到该节点的距离，并更新 `dist` 和 `paths` 数组。

最后，我们输出从起始节点到每个节点的最短路径和经过的元素下标。