Dijkstra's algorithm Java implementation



/** Single-source shortest paths API */
class DijkstraSingleSourceShortestPath {
    // Source 
    private final int s;
    // distTo[v] is length of shortest known path from s to v.
    private final double[] distTo;
    // edgeTo[w] is last edge on shortest known path from s to w
    private final DirectedEdge[] edgeTo;
    private IndexMinPQ pq;
    
    public DijkstraSingleSourceShortestPath(EdgeWeightedDigraph G, int s) {
        // shortest paths from s in graph G
        this.s = s;
        this.distTo = new double[G.V()];
        this.edgeTo = new DirectedEdge[G.V()];
        pq = new IndexMinPQ(G.V());
        for (int v = 0; v < G.V(); v++)
            distTo[v] = Double.POSITIVE_INFINITY;
        distTo[s] = 0.0;
        pq.insert(s, 0.0);
        while (!pq.isEmpty()) { // relax vertices in order of distance from s
            int v = pq.delMin();
            for (DirectedEdge e : G.adj(v))
                relax(e);
        }
    }
    
    /** length of shortest path from s to v */
    double distTo(int v) {
        return distTo[v]; 
    }
    
    /** shortest path from s to v */
    Iterable pathTo(int v) {
        Stack path = new Stack<>();
        DirectedEdge edge = edgeTo[v];
        while(edge != null) {
            path.add(edge);
            edge = edgeTo[edge.from()];
        }
        return path;
    }
    
    /** is there a path from s to v? */
    boolean hasPathTo(int v) {
        
    }
    
    /**
     * Relax edge e = v→w.
     * distTo[v] is length of shortest known path from s to v.
     * distTo[w] is length of shortest known path from s to w.
     * edgeTo[w] is last edge on shortest known path from s to w.
     * If e = v→w gives shorter path to w through v,
     * update both distTo[w] and edgeTo[w].
     */
    private void relax(DirectedEdge e) {
        int v = e.from(), w = e.to();
        if (distTo[w] > distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else pq.insert (w, distTo[w]);
        }
    }
    
    static class EdgeWeightedDigraph {
        private final int V;
        private final List[] adj;
        
        /** create an empty edge-weighted digraph with V vertices */
        public EdgeWeightedDigraph(int V) {
            this.V = V;
            adj = new ArrayList[V]; // // create empty graph with V vertices
            for (int v = 0; v < V; v++) {
                adj[v] = new ArrayList<>();
            }
        }
        
        /** add weighted directed edge e */
        public void addEdge(DirectedEdge e) {
            // add edge e = v→w to only v's adjacency list
            int v = e.from()
            adj[v].add(e);
        }
        
        /** edges pointing from v */
        public Iterable adj(int v) { 
            return adj[v]; 
        }
        
        /** all edges in this graph */
        Iterable edges() {
            Set allEdges = new HashSet<>();
            for(List list : adj) {
                allEdges.addAll(list);
            }
            return allEdges;
        }
        
        /** number of vertices */
        public int V()  {
            return V;
        }
        
        /** number of edges */
        int E()  {
            int edges = 0;
            for(List edge : adj) {
                edges += edge.size();
            }
            return edges;
        }
    }
    
    static class DirectedEdge implements Comparable {
        private final int v;
        private final int w;
        private final double weight;
        
        /** create a weighted edge v-w */
        Edge(int v, int w, double weight) {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }
        
        /** either endpoint */
        int from() {
            return v;
        }
        
        /** the endpoint that's not v */
        int to() {
            return w;
        }
        
        /** compare this edge to that edge */
        public int compareTo(Edge that) {
            if(this.weight < that.weight) {
                return -1;
            } else if(this.weight > that.weight) {
                return 1;
            }
            return 0;
        }
        
        /** the weight */
        double weight() {
            return weight;
        }
        
        /** string representation */
        public String toString() {
            return "Edge: " + v + "-" + w + ", Weight: " + weight;
        }
    }
    
    private static EdgeWeightedDigraph dummyGraph() {
        String[][] input = {
            {"0", "7", "0.16"},
            {"2", "3", "0.17"},
            {"1", "7", "0.19"},
            {"0", "2", "0.26"},
            {"5", "7", "0.28"},
            {"1", "3", "0.29"},
            {"1", "5", "0.32"},
            {"2", "7", "0.34"},
            {"4", "5", "0.35"},
            {"1", "2", "0.36"},
            {"4", "7", "0.37"},
            {"0", "4", "0.38"},
            {"6", "2", "0.40"},
            {"3", "6", "0.52"},
            {"6", "0", "0.58"},
            {"6", "4", "0.93"}
        };
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(8);
        for(int i = 0; i < input.length; i++) {
            int v = Integer.parseInt(input[i][0]);
            int w = Integer.parseInt(input[i][1]);
            double weight = Double.parseDouble(input[i][2]);
            DirectedEdge edge = new DirectedEdge(v, w, weight);
            G.addEdge(edge);
        }
        return G;
    }
    
	public static void main (String[] args) {
		DijkstraSingleSourceShortestPath dijkstraSingleSourceShortestPath = 
		    new DijkstraSingleSourceShortestPath(dummyGraph());
		    System.out.println("dijkstraSingleSourceShortestPath: Weight = " 
		    + dijkstraSingleSourceShortestPath.weight());
		System.out.println("MST edges: ");
		dijkstraSingleSourceShortestPath.edges()
		    .forEach(edge -> 
		        System.out.print(edge.either() + "-" + edge.other(edge.either()) + ", "));
	}
}

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance