java代码分支限界法之单源最短路径问题

以下是使用分支界限法解决单源最短路径问题的Java代码示例：

import java.util.Arrays;
import java.util.PriorityQueue;

class Node implements Comparable<Node> {
    int id;
    int dist;

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

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.dist, o.dist);
    }
}

public class ShortestPath {
    static final int INF = Integer.MAX_VALUE;
    static int[][] graph;
    static int[] dist;
    static boolean[] visited;

    public static void main(String[] args) {
        int n = 5; // 节点数
        int m = 7; // 边数
        int source = 0; // 源节点

        // 构建邻接矩阵
        graph = new int[n][n];
        for (int[] row : graph) {
            Arrays.fill(row, INF);
        }
        graph[0][1] = 10;
        graph[0][3] = 30;
        graph[0][4] = 100;
        graph[1][2] = 50;
        graph[2][4] = 10;
        graph[3][2] = 20;
        graph[3][4] = 60;

        // 初始化距离数组和访问标记数组
        dist = new int[n];
        visited = new boolean[n];
        Arrays.fill(dist, INF);
        dist[source] = 0;

        // 初始化优先队列
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));

        // 分支界限法求解最短路径
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.id;
            if (visited[u]) {
                continue;
            }
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != INF && dist[v] > dist[u] + graph[u][v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.printf("Shortest distance from %d to %d is %d\n", source, i, dist[i]);
        }
    }
}

在上面的代码中，我们首先构建了一个邻接矩阵表示的图，然后使用分支界限法求解最短路径问题，最后输出了每个节点到源节点的最短距离。在实际应用中，我们可以根据需要对代码进行修改和优化，以适应不同的场景。