加权图的最小生成树、最短路径算法 – java实现

加权图相关算法

前言

本文主要介绍加权图算法中两个重要应用:最小生成树和最短路径

求最小生成树时针对的是加权无向图,加权有向图的最小生成树算法成为“最小属树形图”问题,较为复杂,本文不做讨论。

求最短路径则是针对加权有向图,在不同限制条件下,适应不同的算法:

1. 权重非负,采用Dijkstra算法;
2. 不存在环,采用基于拓扑排序的最短路径算法,能够线性空间内解决问题;
3. 不存在负权重环,即如果存在环,环的各条边权重总和不能为负值,采用Bellman-Ford算法。

加权无向图的最小生成树

重新定义最小生成树数据结构,为更好表示,针对边也定义数据结构。

/**
 * 定义加权无向图的边
 */
public class Edge implements Comparable<Edge>{
    private final int v;
    private final int w;
    private final double weight;

    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public int either(){ return v; }
    public int other(int vertex){
        if(v == vertex) return w;
        else return v;
    }
    public double weight(){ return weight; }
    @Override
    public int compareTo(Edge o) { return Double.compare(weight, o.weight); }
    @Override
    public String toString() {
        return "Edge{" +
                "v=" + v +
                ", w=" + w +
                ", weight=" + weight +
                '}';
    }
}
/**
 * 定义加权无向图
 */
public class EdgeWeightedGraph {
    private int V;
    private int E;
    private ArrayList<Edge>[] adj;
    public EdgeWeightedGraph(int V){
        this.V = V;
        adj = (ArrayList<Edge>[]) new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    public EdgeWeightedGraph(Scanner scanner){
        this(scanner.nextInt());
        int E = scanner.nextInt();
        for (int i = 0; i < E; i++) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            double weight = scanner.nextDouble();
            Edge edge = new Edge(v, w, weight);
            addEdge(edge);
        }
    }
    public void addEdge(Edge edge){
        int v = edge.either();
        int w = edge.other(v);
        adj[v].add(edge);
        adj[w].add(edge);
        E++;
    }
    public Iterable<Edge> adj(int v){ return adj[v]; }
    public int V() { return V; }
    public int E() { return E; }
    public Iterable<Edge> edges(){
        ArrayList<Edge> edges = new ArrayList<>();
        for (int v = 0; v < V; v++) {
            for (Edge edge : adj[v]) {
                if(edge.other(v) > v){
                    edges.add(edge);
                }
            }
        }
        return edges;
    }
}
/**
 * 采用Prim算法求加权无向图的最小生成树
 */
public class PrimMST {
    private Edge[] edgeTo;                   // 到达w节点的那条边
    private double[] distTo;                // 到达w节点的边的权重,等价于edgeTo[w].weight()
    private boolean[] marked;               // 标记节点是否在树中
    private TreeMap<Edge, Integer> queue; // 存储未在树中的边
    public PrimMST(EdgeWeightedGraph G){
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        queue = new TreeMap<>();
        for (int i = 0; i < G.V(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        // 初始化,也可采用其他方式
        for (Edge edge : G.adj(0)) {
            queue.put(edge, edge.other(0));
            if(distTo[0] > edge.weight()){
                edgeTo[0] = edge;
                distTo[0] = edge.weight();
            }
        }
        while (!queue.isEmpty()){
            // 从队列中找出边权重最小的边
            Map.Entry<Edge, Integer> minEntry = queue.firstEntry();
            queue.remove(minEntry.getKey());
            visit(G, minEntry.getValue());
        }
    }
    private void visit(EdgeWeightedGraph G, int v){
        // 标记为在书中
        marked[v] = true;
        for (Edge edge : G.adj(v)) {
            int w = edge.other(v);
            if(distTo[w] > edge.weight()){
                Edge pre = edgeTo[w];
                edgeTo[w] = edge;
                distTo[w] = edge.weight();
                if(marked[w]) continue;
                if(null != pre) queue.remove(pre);
                queue.put(edge, w);
            }
        }
    }
    /**
     * 返回最小生成树的边集合
     */
    public Iterable<Edge> edges(){ return Arrays.asList(edgeTo); }
    /**
     * 最小生成树的权重
     */
    public double weight(){
        double weight = 0.0;
        for (Edge edge : edgeTo) {
            weight += edge.weight();
        }
        return weight;
    }
    private void print(){
        for (int v = 0; v < edgeTo.length; v++) {
            Edge edge = edgeTo[v];
            System.out.println(v + " " + edge.other(v));
        }
    }
    public static void main(String[] args) {
        // 输入数据见附录1
        EdgeWeightedGraph G = new EdgeWeightedGraph(new Scanner(System.in));
        PrimMST primMST = new PrimMST(G);
        // 输出结果参见附录2
        System.out.println("最小生成树的边");
        primMST.print();
        System.out.println("树权重总和: " + primMST.weight());
    }
}

加权有向图的最短路径算法

定义加权有向图

/**
 * 加权有向图的边
 */
public class WeightDirectedEdge implements Comparable<WeightDirectedEdge> {
    private int from;
    private int to;
    private double weight;
    public WeightDirectedEdge(int from, int to, double weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    public int from(){ return from; }
    public int to() { return to; }
    public double weight(){ return weight; }
    @Override
    public int compareTo(WeightDirectedEdge o) { return Double.compare(weight, o.weight); }
}
/**
 * 定义加权有向图
 */
public class EdgeWeightDigraph {
    private int V;
    private int E;
    private ArrayList<WeightDirectedEdge>[] adj;
    public EdgeWeightDigraph(int V){
        this.V = V;
        adj = (ArrayList<WeightDirectedEdge>[])new ArrayList[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new ArrayList<>();
        }
    }
    public EdgeWeightDigraph(Scanner scanner){
        this(scanner.nextInt());
        int E = scanner.nextInt();
        for (int v = 0; v < E; v++) {
            int from = scanner.nextInt();
            int to = scanner.nextInt();
            double weight = scanner.nextDouble();
            addEdge(new WeightDirectedEdge(from, to, weight));
        }
    }
    public int V() { return V; }
    public int E() { return E; }
    public Iterable<WeightDirectedEdge> adj(int v){ return adj[v]; }
    public void addEdge(WeightDirectedEdge edge){
        adj[edge.from()].add(edge);
        E++;
    }
}

Dijkstra算法求非负权重有向图最短路径

该算法的使用前提条件是图中不存在权重为负的边,算法的优势在于最坏情况下仍能保证ElogV的时间复杂度。

/**
 * Dijkstra算法求最短路径
 */
public class DijkstraSP {
    private WeightDirectedEdge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;
    private TreeSet<WeightPoint> pq;
    // 定义一个权重和顶点的类,也可采用其他方式表示
    private class WeightPoint implements Comparable<WeightPoint>{
        private double weight;
        private int v;
        public WeightPoint(double weight, int v) {
            this.weight = weight;
            this.v = v;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            WeightPoint that = (WeightPoint) o;
            return v == that.v;
        }
        @Override
        public int hashCode() {
            return Objects.hash(v);
        }
        @Override
        public int compareTo(WeightPoint o) { return Double.compare(weight, o.weight); }
    }
    public DijkstraSP(EdgeWeightDigraph G, int s){
        edgeTo = new WeightDirectedEdge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        pq = new TreeSet<>();
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;
        pq.add(new WeightPoint(0.0, 0));
        while (!pq.isEmpty()){
            WeightPoint point = pq.pollFirst();
            relax(G, point.v);
        }
    }
    private void relax(EdgeWeightDigraph G, int v){
        marked[v] = true;
        for (WeightDirectedEdge edge : G.adj(v)) {
            int w = edge.to();
            if(distTo[w] > distTo[v] + edge.weight()){
                pq.remove(new WeightPoint(distTo[w], w));
                edgeTo[w] = edge;
                distTo[w] = distTo[v] + edge.weight();
                pq.add(new WeightPoint(distTo[w], w));
            }
        }
    }
    public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY; }
    public double distTo(int v) { return distTo[v]; }
    public Iterable<WeightDirectedEdge> pathTo(int v){
        if(!hasPathTo(v)) return null;
        Stack<WeightDirectedEdge> stack = new Stack<>();
        for (WeightDirectedEdge e=edgeTo[v]; e !=null ; e=edgeTo[e.from()])
            stack.add(e);
        return stack;
    }
    public static void main(String[] args) {
        // 输入用例参见附录3
        EdgeWeightDigraph G = new EdgeWeightDigraph(new Scanner(System.in));
        DijkstraSP sp = new DijkstraSP(G, 0);
        // 测试输出结果参见附录4
        System.out.println("0顶点至各点的最短路径: ");
        for (int v = 1; v < G.V(); v++) {
            if (!sp.hasPathTo(v)){
                System.out.println(v + " 无路径");
                continue;
            }
            System.out.print(v + " ");
            for (WeightDirectedEdge e : sp.pathTo(v)) {
                System.out.print(e.from() + "->" + e.to() + " ");
            }
            System.out.println();
        }
    }
}

基于拓扑排序求无环有向图的最短路径

针对无环有向图,按照拓扑排序的顺序,依次relax顶点,既可实现最短路径。算法的优势是时间复杂度为E+V。原理为每次
relax顶点s时,所有能到达s的顶点已经被relax。具体实现略。

Bellman-Ford算法求无负权重环的最短路径

当图形含有负权重边或者环时,这时需要Bellman-Ford算法,算法限制条件是不含有负权重的环。最坏情况下的
时间复杂度是EV。算法依赖有向图的环检测算法。

/**
 * 加权有向图的环检测
 */
public class WeightDigraphCycle {
    private boolean[] onStack;
    private boolean[] marked;
    private WeightDirectedEdge[] edgeTo;
    private Stack<Integer> cycle;
    public WeightDigraphCycle(EdgeWeightDigraph G){
        onStack = new boolean[G.V()];
        marked = new boolean[G.V()];
        edgeTo = new WeightDirectedEdge[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if(!marked[v])
                dfs(G, v);
        }
    }
    private void dfs(EdgeWeightDigraph G, int v){
        marked[v] = true;
        onStack[v] = true;
        for (WeightDirectedEdge edge : G.adj(v)) {
            int w = edge.to();
            if(hasCycle()) return;
            else if(!marked[w]){
                edgeTo[w] = edge;
                dfs(G, w);
            }
            else if(onStack[w]){
                cycle = new Stack<>();
                for (int x = v; x!=w; x = edgeTo[x].from())
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }
    public boolean hasCycle() { return cycle != null; }
    public Stack<Integer> cycle(){ return cycle; }
}
/**
 * Bellman-Ford算法
 * 针对不存在负权重环的加权有向图,求最短路径
 * 算法依赖有向图的环检测
 */
public class BellmanFordSP {
    private double[] distTo;
    private WeightDirectedEdge[] edgeTo;
    private boolean[] onQ;
    private TreeSet<WeightPoint> pq;
    private Stack<Integer> cycle;
    private int cost;
    // 定义一个权重和顶点的类
    private class WeightPoint implements Comparable<WeightPoint>{
        private double weight;  // 等价于distTo[v]
        private int v;
        public WeightPoint(double weight, int v) {
            this.weight = weight;
            this.v = v;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            WeightPoint that = (WeightPoint) o;
            return v == that.v;
        }
        @Override
        public int hashCode() {
            return Objects.hash(v);
        }
        @Override
        public int compareTo(WeightPoint o) { return Double.compare(weight, o.weight); }
    }
    public BellmanFordSP(EdgeWeightDigraph G, int s){
        distTo = new double[G.V()];
        edgeTo = new WeightDirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        pq = new TreeSet<>();
        for (int i = 0; i < G.V(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;
        pq.add(new WeightPoint(0.0, s));
        onQ[s] = true;
        while (!pq.isEmpty() && !hasNagetiveCycle()){
            WeightPoint weightPoint = pq.pollFirst();
            relax(G, weightPoint.v);
        }
    }
    private void relax(EdgeWeightDigraph G, int v){
        onQ[v] = false;
        for (WeightDirectedEdge directedEdge : G.adj(v)) {
            if(hasNagetiveCycle()) return;
            int w = directedEdge.to();
            if(distTo[w] > distTo[v] + directedEdge.weight()){
                distTo[w] = distTo[v] + directedEdge.weight();
                edgeTo[w] = directedEdge;
                if(!onQ[w]){
                    onQ[w] = true;
                    pq.add(new WeightPoint(directedEdge.weight(), w));
                }
            }
            if(cost++ % G.V() == 0)
                findNagetiveCycle();
        }
    }
    private boolean hasNagetiveCycle(){ return cycle != null; }
    private void findNagetiveCycle(){
        int V = edgeTo.length;
        EdgeWeightDigraph digraph = new EdgeWeightDigraph(V);
        for (int i = 0; i < V; i++) {
            if(edgeTo[i] != null){
                digraph.addEdge(edgeTo[i]);
            }
        }
        WeightDigraphCycle weightDigraphCycle = new WeightDigraphCycle(digraph);
        if (weightDigraphCycle.hasCycle())
            cycle = weightDigraphCycle.cycle();
    }
    public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY; }
    public Iterable<WeightDirectedEdge> pathTo(int v){
        if(!hasPathTo(v)) return null;
        ArrayDeque<WeightDirectedEdge> paths = new ArrayDeque<>();
        for (WeightDirectedEdge e = edgeTo[v]; e!= null; e=edgeTo[e.from()]){
            paths.push(e);
        }
        return paths;
    }
    public static void main(String[] args) {
        // 测试输入用例参见附录5
        EdgeWeightDigraph digraph = new EdgeWeightDigraph(new Scanner(System.in));
        BellmanFordSP bellmanFordSP = new BellmanFordSP(digraph, 5);
        // 输出用例参见附录6
        if(bellmanFordSP.hasNagetiveCycle()){
            System.out.println("含有负权重环");
        } else {
            for (int i = 1; i < digraph.V(); i++) {
                System.out.print("5 到顶点 " + i + "是否有路径: " + (bellmanFordSP.hasPathTo(i) ? "是" : "否"));
                if(bellmanFordSP.hasPathTo(i)){
                    System.out.print(", 最短路径为:");
                    for (WeightDirectedEdge directedEdge : bellmanFordSP.pathTo(i)) {
                        System.out.print(directedEdge.from() + "->" + directedEdge.to() + " ");
                    }
                }
                System.out.println();
            }
        }
    }
}

附录1 加权无向图的输入用例

附录2 最小生成树的测试输出

最小生成树的边
0 7
1 7
2 3
3 2
4 5
5 7
6 2
7 1
树权重总和: 1.9100000000000001

附录3 Dijkstra输入用例

9
15
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

附录4 Dijkstra输出用例

0顶点至各点的最短路径: 
1 5->1 4->5 0->4 
2 0->2 
3 7->3 2->7 0->2 
4 0->4 
5 4->5 0->4 
6 3->6 7->3 2->7 0->2 
7 2->7 0->2 
8 无路径

附录5 Bellman-Ford输入用例1

8
15
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 -1.20
3 6 0.52
6 0 -1.40
6 4 -1.25

附录6 Bellman-Ford输出用例1

5 到顶点 1是否有路径: 是, 最短路径为:5->1 
5 到顶点 2是否有路径: 是, 最短路径为:5->1 1->3 3->6 6->2 
5 到顶点 3是否有路径: 是, 最短路径为:5->1 1->3 
5 到顶点 4是否有路径: 是, 最短路径为:5->1 1->3 3->6 6->4 
5 到顶点 5是否有路径: 是, 最短路径为:
5 到顶点 6是否有路径: 是, 最短路径为:5->1 1->3 3->6 
5 到顶点 7是否有路径: 是, 最短路径为:5->1 1->3 3->6 6->4 4->7

附录7 Bellman-Ford输入用例2,含有负权重环

附录8 Bellman-Ford输出用例2,含有负权重环