单源最短路径问题 输入图顶点个数为5时，图的路径长度为以下数组： 0，8，1，1，5 1，0，1，1，2 1，1，0，4，1 1，1，6，0，1 1，3，9，2，0 根据以上程序范例，请设计程序计算出每个节点的最短距离和前驱节点分别是多少？ 用java代码

单源最短路径问题通常通过Dijkstra算法或Floyd-Warshall算法解决。给定的是邻接矩阵表示的图，我们可以使用Dijkstra算法，因为对于非负权重图，它是最有效的。以下是使用Java实现Dijkstra算法的一个示例：

import java.util.*;

class ShortestPath {
    private int V; // 图的顶点数
    private int[] dist; // 存储最短距离
    private boolean[] visited; // 标记节点是否已访问
    private int[] parent; // 存储最短路径的前驱节点

    public ShortestPath(int v) {
        V = v;
        dist = new int[V];
        visited = new boolean[V];
        Arrays.fill(visited, false);
        parent = new int[V];
    }

    void dijkstra(int[][] graph, int src) {
        for (int i = 0; i < V; ++i)
            dist[i] = Integer.MAX_VALUE;

        dist[src] = 0;
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, visited);

            visited[u] = true;

            for (int v = 0; v < V; v++)
                if (!visited[v] && graph[u][v] != 0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    parent[v] = u;
                }
        }
    }

    int minDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && dist[v] <= min)
                min = dist[v], min_index = v;
        return min_index;
    }

    // 输出结果
    void printSolution() {
        System.out.println("Vertex\t Distance from Source\t Predecessor");
        for (int i = 0; i < V; ++i)
            System.out.println(i + "\t\t" + dist[i] + "\t\t" + (parent[i] == -1 ? "None" : i));
    }

    public static void main(String[] args) {
        int[][] graph = { { 0, 8, 1, 1, 5 }, { 8, 0, 1, 1, 2 }, { 1, 1, 0, 4, 1 }, { 1, 1, 6, 0, 1 }, { 5, 3, 9, 2, 0 } };
        ShortestPath sp = new ShortestPath(graph.length);
        sp.dijkstra(graph, 0); // 从第一个节点开始搜索
        sp.printSolution();
    }
}

在这个例子中，我们首先创建了一个`ShortestPath`类，然后定义了Dijkstra算法所需的辅助函数。`dijkstra`方法接收邻接矩阵和源节点作为输入，并通过不断更新`dist`数组找到未访问节点的最短路径。最后，`printSolution`方法用于打印每个节点的距离及其前驱节点。

运行这个代码，你会得到每个节点到源节点的最短距离以及它们的前驱节点。注意这里假设所有边的权重都是正整数，如果包含负权重，需要使用其他算法如Bellman-Ford。