单源路径分支界限java_分支限界法—单源最短路径问题

单源最短路径问题是指在给定的带权有向图中，找到从源节点到其他所有节点的最短路径。分支限界法可以用来解决单源最短路径问题。

以下是基于Java语言的单源最短路径问题的分支限界算法实现：

import java.util.*;

public class ShortestPath {
    private int n; // 图中节点数
    private int[][] graph; // 图的邻接矩阵
    private int[] dist; // 存储源节点到其他节点的距离
    private boolean[] visited; // 标记节点是否已经被访问

    // 构造函数
    public ShortestPath(int n, int[][] graph) {
        this.n = n;
        this.graph = graph;
        this.dist = new int[n];
        this.visited = new boolean[n];
    }

    // 分支限界算法求解单源最短路径
    public void shortestPath(int source) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.dist)); // 优先队列，按照节点距离排序
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为正无穷
        dist[source] = 0; // 源节点到自身的距离为0
        pq.offer(new Node(source, 0)); // 将源节点加入优先队列

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.u;
            visited[u] = true; // 标记节点已经被访问

            // 遍历u的所有邻居节点
            for (int v = 0; v < n; v++) {
                if (graph[u][v] > 0 && !visited[v]) { // v是u的邻居节点且没有被访问过
                    int newDist = dist[u] + graph[u][v]; // 计算新的距离
                    if (newDist < dist[v]) { // 如果新的距离比原来的距离更短，更新距离并加入优先队列
                        dist[v] = newDist;
                        pq.offer(new Node(v, newDist));
                    }
                }
            }
        }
    }

    // 内部类，表示节点
    private static class Node {
        int u; // 节点编号
        int dist; // 节点距离

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

    // 测试
    public static void main(String[] args) {
        int n = 5;
        int[][] graph = new int[][] {
                {0, 10, 0, 30, 100},
                {0, 0, 50, 0, 0},
                {0, 0, 0, 0, 10},
                {0, 0, 20, 0, 60},
                {0, 0, 0, 0, 0}
        };
        ShortestPath sp = new ShortestPath(n, graph);
        sp.shortestPath(0);
        System.out.println(Arrays.toString(sp.dist)); // 输出源节点到其他节点的最短距离
    }
}

以上代码实现了分支限界算法求解单源最短路径问题，利用优先队列按照节点距离排序，遍历每个节点的邻居节点，更新距离并加入优先队列。最终输出源节点到其他节点的最短距离。