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

单源最短路径问题是指在给定的带权有向图中，找到从源节点到其他所有节点的最短路径。分支限界法可以用来解决单源最短路径问题。 以下是基于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)); // 输出源节点到其他节点的最短距离 } } ``` 以上代码实现了分支限界算法求解单源最短路径问题，利用优先队列按照节点距离排序，遍历每个节点的邻居节点，更新距离并加入优先队列。最终输出源节点到其他节点的最短距离。

好的，我们可以在上面的代码基础上进行修改，输出s点到每个节点的最短路径长度以及到达路径。修改后的代码如下： ```java import java.util.*; public class ShortestPath { private int n; // 图中节点数 private int[][] graph; // 图的邻接矩阵 private int[] dist; // 存储源节点到其他节点的距离 private boolean[] visited; // 标记节点是否已经被访问 private int[] parent; // 存储每个节点的父节点 // 构造函数 public ShortestPath(int n, int[][] graph) { this.n = n; this.graph = graph; this.dist = new int[n]; this.visited = new boolean[n]; this.parent = new int[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; parent[v] = u; // 更新v的父节点为u pq.offer(new Node(v, newDist)); } } } } } // 输出s点到其他点的最短路径长度及路径 public void printShortestPath(int source, int[] targets) { for (int target : targets) { System.out.print("Shortest path from " + (char)('a' + source) + " to " + (char)('a' + target) + ": "); if (dist[target] == Integer.MAX_VALUE) { // 如果无法到达，输出无穷大 System.out.println("inf"); } else { System.out.print(dist[target] + " ["); // 输出最短路径长度 List<Integer> path = new ArrayList<>(); int u = target; while (u != source) { // 从目标节点往回找父节点，得到到达路径 path.add(u); u = parent[u]; } path.add(source); Collections.reverse(path); for (int i = 0; i < path.size(); i++) { // 输出到达路径 System.out.print((char)('a' + path.get(i))); if (i < path.size() - 1) { System.out.print(" -> "); } } System.out.println("]"); } } } // 内部类，表示节点 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 = 8; int[][] graph = new int[][] { {0, 4, 1, 0, 0, 0, 0, 0}, {4, 0, 2, 5, 0, 0, 0, 0}, {1, 2, 0, 8, 10, 0, 0, 0}, {0, 5, 8, 0, 2, 6, 0, 0}, {0, 0, 10, 2, 0, 3, 9, 0}, {0, 0, 0, 6, 3, 0, 0, 5}, {0, 0, 0, 0, 9, 0, 0, 7}, {0, 0, 0, 0, 0, 5, 7, 0} }; ShortestPath sp = new ShortestPath(n, graph); sp.shortestPath(0); int[] targets = {0, 1, 2, 3, 4, 5, 6, 7}; sp.printShortestPath(0, targets); // 输出源节点到其他节点的最短路径长度及到达路径 } } ``` 以上代码输出s点到a,b,c,d,e,f,g,h点的最短路径长度及到达路径。