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

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

具体来说，分支限界法可以通过建立一个优先队列来遍历所有可能的路径，并且在队列中保留当前最短的路径。每次从队列中取出一个路径，然后延伸它，生成新的路径，并将新的路径加入到队列中。如果新路径的长度比当前最短路径长，那么就可以直接丢弃这个路径。

Java中可以使用PriorityQueue来实现优先队列。具体实现过程如下：

1. 定义一个节点类Node，表示图中的节点，包括节点编号和到源节点的距离。

class Node implements Comparable<Node> {
    int id; // 节点编号
    int distance; // 到源节点的距离

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

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

2. 定义一个图类Graph，表示加权有向图，包括节点数和边的信息。

class Graph {
    int V; // 节点数
    List<int[]>[] adj; // 邻接表，存储边的信息

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v, int w) {
        adj[u].add(new int[]{v, w}); // 添加边
    }
}

3. 定义一个Dijkstra类，表示单源最短路径问题的解法。

class Dijkstra {
    int[] distTo; // 存储每个节点到源节点的距离
    PriorityQueue<Node> pq; // 优先队列

    public Dijkstra(Graph graph, int s) {
        distTo = new int[graph.V];
        Arrays.fill(distTo, Integer.MAX_VALUE);
        distTo[s] = 0;

        pq = new PriorityQueue<>();
        pq.offer(new Node(s, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int u = node.id;

            for (int[] edge : graph.adj[u]) {
                int v = edge[0], w = edge[1];
                if (distTo[u] + w < distTo[v]) { // 如果通过u可以到达v的距离更短
                    distTo[v] = distTo[u] + w;
                    pq.offer(new Node(v, distTo[v]));
                }
            }
        }
    }

    public int[] getDistTo() {
        return distTo;
    }
}

4. 使用示例：

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 3, 2);
        graph.addEdge(2, 4, 4);
        graph.addEdge(3, 1, 3);
        graph.addEdge(3, 2, 9);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 0, 7);
        graph.addEdge(4, 2, 6);

        Dijkstra dijkstra = new Dijkstra(graph, 0);
        int[] distTo = dijkstra.getDistTo();
        System.out.println(Arrays.toString(distTo)); // [0, 8, 9, 5, 7]
    }
}

在这个例子中，我们构建了一个有向图，然后使用Dijkstra算法求解从节点0出发到其他所有节点的最短距离。最终得到的结果为[0, 8, 9, 5, 7]，表示节点0到其他节点的最短距离分别为0、8、9、5、7。