单源最短路径问题

问题描述

• 给定一个带权有向图 G=(V, E)，其中每条边的权是非负实数，另外，该给定 V 中的一个节点，称为源，现在要计算从源到所有其他各节点的最短路长度，这里路的长度是指路上各权值和，这个问题通常称为单源最短路径问题。

算法设计

• 算法从图 G 的源节点 s 和空优先队列开始，结点 s 被扩展后，它的儿子结点被依次插入堆中，此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有节点。
• 如果从当前扩展结点 i 到节点 j 有边可达，且从源出发，途经节点 i 再到节点 j 的所相应的路径的长度小于当前最优路径长度，则将该节点作为活结点插入到活结点优先队列中，这个结点的扩展过程一直继续到活结点优先队列为空时为止。
• 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。
• 在算法中，利用结点间的控制关系进行剪枝，从源节点 s 出发，2 条不同路径到达图 G 的同一节点，由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。

代码实现

流程图

. png)

public class test {

    public static void main(String[] args) {
        // 节点个数。
        int n = 5;
        // 邻接矩阵。
        float[][] a = {
                {-1, 10, -1, 30, 100},
                {-1, -1, 50, -1, -1},
                {-1, -1, -1, -1, 10},
                {-1, -1, 20, -1, 60},
                {-1, -1, -1, -1, -1}
        };
        float[] dist = new float[n];
        int[] prev = new int[n];
        // 节点从1开始。
        int v = 0;
        shortest(a, v, dist, prev);
    }

    public static class ExtendNode implements Comparable<ExtendNode> {
        int id;
        float length;

        public ExtendNode(int ii, float ll) {
            id = ii;
            length = ll;
        }

        @Override
        public int compareTo(ExtendNode o) {
            return Float.compare(length, o.length);
        }
    }

    public static void shortest(float[][] a, int v, float[] dist, int[] prev) {
        int n = prev.length;
        // 用LinkedList存储最小堆。
        LinkedList<ExtendNode> nodes = new LinkedList<>();
        ExtendNode eNode = new ExtendNode(v, 0);
        for (int j = 0; j < n; j++) {
            dist[j] = Float.MAX_VALUE;
        }
        while (true) {
            // 在问题解空间中寻找扩展节点。
            for (int j = 0; j < n; j++) {
                // 节点i到j可达，同时长度小于dist[j]
                if (a[eNode.id][j] != -1 && eNode.length + a[eNode.id][j] < dist[j]) {
                    dist[j] = eNode.length + a[eNode.id][j];
                    prev[j] = eNode.id;
                    // 初始化扩展节点并存入最小堆中。
                    ExtendNode e = new ExtendNode(j, dist[j]);
                    nodes.add(e);
                    // 将最小堆重新排序。
                    Collections.sort(nodes);
                }
            }
            if (nodes.isEmpty())
                break;
            else {
                // 从最小堆中取下一个扩展结点，该扩展节点的距离是所有扩展节点中最小的。
                eNode = nodes.poll();
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.println("到" + i + "节点的最短距离是：" + dist[i] + " 前驱节点为：" + (1 + prev[i]));
        }
    }

}

• public static void shortest(float[][] a, int v, float[] dist, int[] prev) ：计算从源节点到图上其他节点的最短路径。
  • float[][] a：求解图的邻接矩阵。
  • int v：源节点。
  • float[] dist：保存从源节点到其他节点的距离。
  • p[j]：记录从源节点到其他节点的路径上的前驱节点。
• public static class ExtendNode implements Comparable<ExtendNode>：扩展节点。
  • int id：节点编号。
  • float length：源节点到该扩展节点的距离。