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 < 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 p

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() < G.V()-1) { // repeatedly delete the min weight edge e = v–w from PQ Edge edge = pq.poll(); // greedily add edges to MST int v = edge.either(), w = edge.other(v); // ignore if both endpoints in T if(visi

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() < G.V()-1) { Edge e = pq.poll(); // greedily add edges to MST int v = e.either(), w = e.other(v); if (!uf.isConnected(v, w)) { // Check that edge v–w does not create cycle // merge sets uf.union(v, w); // add edge to MST mst.add(e); // add weight in total weight count

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