Minimum spanning tree and shortest path algorithm for weighted graph - java implementation

Weighted Graph Correlation Algorithm

foreword

This paper mainly introduces two important applications of weighted graph algorithm: minimum spanning tree and shortest path.

The weighted undirected graph is used to find the minimum spanning tree, and the minimum spanning tree algorithm of the weighted directed graph becomes the "minimum genus tree graph" problem, which is more complicated and will not be discussed in this article.

Finding the shortest path is for weighted directed graphs and adapts to different algorithms under different constraints:

1. The weight is non-negative, using Dijkstra algorithm;
2. There is no ring, and the shortest path algorithm based on topological sorting can be used to solve the problem in linear space;
3. There is no negative weight ring, that is, if there is a ring, the sum of the weights of the edges of the ring cannot be negative. Bellman-Ford algorithm.

Minimum Spanning Tree for Weighted Undirected Graphs

Redefine the minimum spanning tree data structure, and also define the data structure for the edges for better representation.

/**
 * Define the edges of a weighted undirected graph
 */
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 +
                '}';
    }
}
/**
 * Define Weighted Undirected Graph
 */
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;
    }
}
/**
 * Using Prim's Algorithm to Find the Minimum Spanning Tree of Weighted Undirected Graph
 */
public class PrimMST {
    private Edge[] edgeTo;                   // the edge that reaches the w node
    private double[] distTo;                // The weight of the edge reaching the w node, equivalent to edgeTo[w].weight()
    private boolean[] marked;               // mark whether the node is in the tree
    private TreeMap<Edge, Integer> queue; // Store edges not in the tree
    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;
        }
        // Initialization, other methods can also be used
        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()){
            // Find the edge with the smallest edge weight from the queue
            Map.Entry<Edge, Integer> minEntry = queue.firstEntry();
            queue.remove(minEntry.getKey());
            visit(G, minEntry.getValue());
        }
    }
    private void visit(EdgeWeightedGraph G, int v){
        // marked as in book
        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);
            }
        }
    }
    /**
     * Returns the set of edges for the minimum spanning tree
     */
    public Iterable<Edge> edges(){ return Arrays.asList(edgeTo); }
    /**
     * Minimum spanning tree weights
     */
    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) {
        // For input data see appendix 1
        EdgeWeightedGraph G = new EdgeWeightedGraph(new Scanner(System.in));
        PrimMST primMST = new PrimMST(G);
        // See Appendix 2 for output results
        System.out.println("Minimum spanning tree edge");
        primMST.print();
        System.out.println("Sum of tree weights: " + primMST.weight());
    }
}

Shortest Path Algorithm for Weighted Directed Graphs

Define Weighted Directed Graph

/**
 * weighted directed graph edges
 */
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); }
}
/**
 * Define Weighted Directed Graph
 */
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's algorithm for finding the shortest path in a directed graph with non-negative weights

The premise of using this algorithm is that there is no edge with negative weight in the graph. The advantage of the algorithm is that the time complexity of ElogV can still be guaranteed in the worst case.

/**
 * Dijkstra Algorithm to find the shortest path
 */
public class DijkstraSP {
    private WeightDirectedEdge[] edgeTo;
    private double[] distTo;
    private boolean[] marked;
    private TreeSet<WeightPoint> pq;
    // Defines a class of weights and vertices, which can also be represented in other ways
    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) {
        // See Appendix 3 for input use cases
        EdgeWeightDigraph G = new EdgeWeightDigraph(new Scanner(System.in));
        DijkstraSP sp = new DijkstraSP(G, 0);
        // See Appendix 4 for test output results
        System.out.println("0 shortest path from vertex to point: ");
        for (int v = 1; v < G.V(); v++) {
            if (!sp.hasPathTo(v)){
                System.out.println(v + " no path");
                continue;
            }
            System.out.print(v + " ");
            for (WeightDirectedEdge e : sp.pathTo(v)) {
                System.out.print(e.from() + "->" + e.to() + " ");
            }
            System.out.println();
        }
    }
}

Finding the Shortest Path of Acyclic Directed Graph Based on Topological Sort

For acyclic directed graphs, the shortest path can be achieved by relax ing the vertices in turn in the order of topological sorting. The advantage of the algorithm is that the time complexity is E+V. The principle is every time
When relaxing vertex s, all vertices that can reach s have been relaxed. The specific implementation is omitted.

Bellman-Ford Algorithm to Find Shortest Paths Without Negative Weight Rings

When the graph contains negative-weight edges or rings, the Bellman-Ford algorithm is required, and the algorithm is limited in that it does not contain negative-weight rings. worst case
The time complexity is EV. The algorithm relies on the ring detection algorithm for directed graphs.

/**
 * Ring Detection for Weighted Directed Graphs
 */
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 algorithm
 * Find the shortest path for a weighted directed graph without negative weight cycles
 * Algorithms rely on ring detection for directed graphs
 */
public class BellmanFordSP {
    private double[] distTo;
    private WeightDirectedEdge[] edgeTo;
    private boolean[] onQ;
    private TreeSet<WeightPoint> pq;
    private Stack<Integer> cycle;
    private int cost;
    // Define a class for weights and vertices
    private class WeightPoint implements Comparable<WeightPoint>{
        private double weight;  // Equivalent to 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) {
        // See Appendix 5 for test input cases
        EdgeWeightDigraph digraph = new EdgeWeightDigraph(new Scanner(System.in));
        BellmanFordSP bellmanFordSP = new BellmanFordSP(digraph, 5);
        // See Appendix 6 for output use cases
        if(bellmanFordSP.hasNagetiveCycle()){
            System.out.println("Contains negative weight loops");
        } else {
            for (int i = 1; i < digraph.V(); i++) {
                System.out.print("5 to the vertex " + i + "Is there a path: " + (bellmanFordSP.hasPathTo(i) ? "Yes" : "no"));
                if(bellmanFordSP.hasPathTo(i)){
                    System.out.print(", The shortest path is:");
                    for (WeightDirectedEdge directedEdge : bellmanFordSP.pathTo(i)) {
                        System.out.print(directedEdge.from() + "->" + directedEdge.to() + " ");
                    }
                }
                System.out.println();
            }
        }
    }
}

Appendix 1 Input Use Cases for Weighted Undirected Graphs

Appendix 2 Minimum Spanning Tree Test Output

Minimum spanning tree edge
0 7
1 7
2 3
3 2
4 5
5 7
6 2
7 1
 Sum of tree weights: 1.9100000000000001

Appendix 3 Dijkstra Input Use Cases

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

Appendix 4 Dijkstra Output Use Case

0 shortest path from vertex to point: 
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 no path

Appendix 5 Bellman-Ford Input Use Case 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

Appendix 6 Bellman-Ford Output Use Case 1

5 Is there a path to vertex 1: Yes, The shortest path is: 5->1 
5 Is there a path to vertex 2: Yes, The shortest path is: 5->1 1->3 3->6 6->2 
5 Is there a path to vertex 3: Yes, The shortest path is: 5->1 1->3 
5 Is there a path to vertex 4: Yes, The shortest path is: 5->1 1->3 3->6 6->4 
5 Is there a path to vertex 5: Yes, The shortest path is:
5 Is there a path to vertex 6: Yes, The shortest path is: 5->1 1->3 3->6 
5 Is there a path to vertex 7: Yes, The shortest path is: 5->1 1->3 3->6 6->4 4->7

Appendix 7 Bellman-Ford Input Case 2 with Negative Weight Loops

Appendix 8 Bellman-Ford Output Case 2 with Negative Weight Loops

Tags: Algorithm

Posted by chedong on Sat, 14 May 2022 19:15:58 +0300