用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;
        }
    }
}