采用分支限界法编程求源点0到终点6的最短路径及其路径长度。java实现

以下是基于分支限界法求解源点0到终点6的最短路径及其路径长度的Java实现：

import java.util.*;

public class ShortestPath {

    static int[][] graph = {{0, 2, 1, 4, 5, 1, 6}, {2, 0, 4, 1, 3, 2, 0}, {1, 4, 0, 1, 2, 3, 0},
                            {4, 1, 1, 0, 0, 1, 0}, {5, 3, 2, 0, 0, 2, 0}, {1, 2, 3, 1, 2, 0, 0}, {6, 0, 0, 0, 0, 0, 0}};

    static int start = 0; // 源点
    static int end = 6; // 终点

    static class Node implements Comparable<Node> {
        int index; // 当前节点的编号
        int distance; // 从源点到当前节点的距离

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

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

    public static void main(String[] args) {
        int[] path = shortestPath();
        System.out.println("最短路径为：" + Arrays.toString(path));
        System.out.println("路径长度为：" + path[end]);
    }

    private static int[] shortestPath() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0));

        int[] distances = new int[graph.length];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        int[] preNodes = new int[graph.length];
        Arrays.fill(preNodes, -1);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            int currIndex = curr.index;
            int currDistance = curr.distance;

            if (currIndex == end) { // 已经找到最短路径，退出循环
                break;
            }

            for (int i = 0; i < graph[currIndex].length; i++) {
                if (graph[currIndex][i] != 0 && currDistance + graph[currIndex][i] < distances[i]) {
                    distances[i] = currDistance + graph[currIndex][i];
                    preNodes[i] = currIndex;
                    queue.offer(new Node(i, distances[i]));
                }
            }
        }

        // 从终点往前推，获取最短路径
        int[] path = new int[graph.length];
        int index = end;
        int count = 0;
        while (index != -1) {
            path[count++] = index;
            index = preNodes[index];
        }
        for (int i = 0; i < count / 2; i++) {
            int temp = path[i];
            path[i] = path[count - i - 1];
            path[count - i - 1] = temp;
        }

        return path;
    }
}

在上述代码中，我们采用了优先队列来存储待扩展节点，并按照节点到源点的距离从小到大排序，每次取出距离最小的节点进行扩展。distances数组用于记录源点到各个节点的最短路径长度，preNodes数组用于记录每个节点在最短路径中的前一个节点。最后，我们从终点往前推，获取最短路径，并将路径上的节点编号存储在path数组中。