Up to date

 

 

  Shorted Path Properties Dijkstra's algorithm ( Java code ) edge-weighted Direct Acyclic Graphs (DAGs) Negative Weights Shortest paths summary Dijkstra’s algorithm. ・Nearly linear-time when weights are nonnegative. ・Generalization encompasses DFS, BFS, and Prim.  Acyclic edge-weighted digraphs. ・Arise in applications. ・Faster than Dijkstra’s algorithm. ・Negative weights are no problem.  Negative weights and negative cycles. ・Arise in applications. ・If no negative cycles, can find shortest paths via Bellman-Ford. ・If negative cycles, can find one via Bellman-Ford.  Shortest-paths is a broadly useful problem-solving model.

/** 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 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 ...

import java.util.Queue; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Set; import java.util.HashSet; import java.util.List; import java.util.ArrayList; class PrimMinimumSpanningTreeLazy { private boolean[] visited; // MST vertices private Queue mst; // MST edges private Queue pq; // PriorityQueue of edges private double weight; public PrimMinimumSpanningTreeLazy(EdgeWeightedGraph G) { this.visited = new boolean[G.V()]; this.mst = new ArrayDeque (); this.pq = new PriorityQueue (); // assume G is connected visit(G, 0); while (!pq.isEmpty() && mst.size() edges() { return mst; } public double weight() { return weight; } private void visit(EdgeWeightedGraph G, int v) { visited[v] = true; // add v to T // for each edge e = v–w, add to PQ if w not already in T for(Edge edge : G.adj(v)) { ...

import java.util.Queue; import java.util.ArrayDeque; import java.util.PriorityQueue; import java.util.Set; import java.util.HashSet; import java.util.List; import java.util.ArrayList; class KruskalMinimumSpanningTree { private Queue mst = new ArrayDeque (); private double weight; public KruskalMinimumSpanningTree(EdgeWeightedGraph G) { // build priority queue Queue pq = new PriorityQueue (); for (Edge e : G.edges()) { pq.add(e); } UnionFind uf = new UnionFind(G.V()); while (!pq.isEmpty() && mst.size() edges() { return mst; } public double weight() { return weight; } static class EdgeWeightedGraph { private final int V; private final List [] adj; /** create an empty graph with V vertices */ public EdgeWeightedGraph(int V) { this.V = V; adj = new ArrayList[V]; // // create empty graph with V ...

  Greedy MST algorithm: efficient implementations 1. Kruskal's algorithm ( Code ) 2. Prim's algorithm (1.   lazy implementation , 2.  ) 3. Borüvka's algorithm