用Java实现Dijkstra中k条最短路径的无向图

Dijkstra算法是一种用于求解单源最短路径问题的经典算法，它可以找到从起点到其他所有节点的最短路径。在无向图中，Dijkstra算法可以用于求解k条最短路径，即从起点到其他节点的k条最短路径。

在Java中，可以使用图的邻接矩阵或邻接表来表示无向图，并通过实现Dijkstra算法来求解k条最短路径。以下是用Java实现Dijkstra算法求解k条最短路径的无向图的示例代码：

import java.util.*;

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

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 5, 1, INF},
            {2, 0, 3, 2, INF},
            {5, 3, 0, 3, 1},
            {1, 2, 3, 0, 1},
            {INF, INF, 1, 1, 0}
        };
        int start = 0; // 起点
        int k = 3; // k条最短路径

        List<List<Integer>> shortestPaths = findKShortestPaths(graph, start, k);
        for (int i = 0; i < shortestPaths.size(); i++) {
            System.out.println("Path " + (i + 1) + ": " + shortestPaths.get(i));
        }
    }

    public static List<List<Integer>> findKShortestPaths(int[][] graph, int start, int k) {
        int n = graph.length; // 节点数
        List<List<Integer>> shortestPaths = new ArrayList<>();

        // 初始化距离数组和路径数组
        int[] dist = new int[n];
        int[][] paths = new int[n][n];
        for (int i = 0; i < n; i++) {
            dist[i] = INF;
            Arrays.fill(paths[i], -1);
        }

        // Dijkstra算法
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.dist));
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.vertex;
            int d = curr.dist;

            if (d > dist[u]) {
                continue;
            }

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != INF) {
                    int newDist = d + graph[u][v];

                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        paths[v] = Arrays.copyOf(paths[u], n);
                        paths[v][v] = u;

                        pq.offer(new Node(v, newDist));
                    } else if (newDist == dist[v] && paths[v][v] == -1) {
                        paths[v] = Arrays.copyOf(paths[u], n);
                        paths[v][v] = u;

                        pq.offer(new Node(v, newDist));
                    }
                }
            }
        }

        // 构造k条最短路径
        for (int i = 0; i < n; i++) {
            if (i != start && paths[i][i] != -1) {
                List<Integer> path = new ArrayList<>();
                int curr = i;

                while (curr != start) {
                    path.add(0, curr);
                    curr = paths[curr][curr];
                }

                path.add(0, start);
                shortestPaths.add(path);

                if (shortestPaths.size() == k) {
                    break;
                }
            }
        }

        return shortestPaths;
    }

    static class Node {
        int vertex;
        int dist;

        public Node(int vertex, int dist) {
            this.vertex = vertex;
            this.dist = dist;
        }
    }
}

这段代码实现了Dijkstra算法来求解k条最短路径的无向图。其中，graph是无向图的邻接矩阵表示，start是起点，k是要求解的最短路径条数。函数findKShortestPaths返回一个包含k条最短路径的列表。

该算法使用了优先队列来优化查找最短路径的过程，通过不断更新距离数组和路径数组来求解最短路径。最后，根据路径数组构造k条最短路径。

请注意，这段代码只是一个示例，实际应用中可能需要根据具体情况进行适当的修改和优化。

推荐的腾讯云相关产品：腾讯云云服务器（ECS）、腾讯云云数据库MySQL、腾讯云对象存储（COS）等。你可以通过访问腾讯云官方网站（https://cloud.tencent.com/）了解更多关于这些产品的详细信息。