public class BellmanFordLP {
private double[] distTo;             // distTo[v] = distance of longest s->v path
private DirectedEdge[] edgeTo;       // edgeTo[v] = last edge on longest s->v path
private boolean[] onQueue;          // onQueue[v] = is v currently on the queue?
private Queue<Integer> queue;       // queue of vertices to relax
private int cost;                   // number of calls to relax()
private Iterable<DirectedEdge> cycle; // negative cycle (or null if no such cycle)

/**
* Computes a longest paths tree from {@code s} to every other vertex in
* the edge-weighted digraph {@code G}.
* @param G the acyclic digraph
* @param s the source vertex
* @throws IllegalArgumentException unless {@code 0 <= s < V}
*/
public BellmanFordLP(EdgeWeightedDigraph G, int s) {
   distTo = new double[G.V()];
   edgeTo = new DirectedEdge[G.V()];
   onQueue = new boolean[G.V()];
   for (int v = 0; v < G.V(); v++)
         distTo[v] = Double.NEGATIVE_INFINITY;
   distTo[s] = 0.0;

   // Bellman-Ford algorithm
   queue = new Queue<Integer>();
   queue.enqueue(s);
   onQueue[s] = true;
   while (!queue.isEmpty() && !hasNegativeCycle()) {
         int v = queue.dequeue();
         onQueue[v] = false;
         relax(G, v);
   }

   assert check(G, s);
}

// relax vertex v and put other endpoints on queue if changed
private void relax(EdgeWeightedDigraph G, int v) {
   for (DirectedEdge e : G.adj(v)) {
         int w = e.to();
         if (distTo[w] < distTo[v] + e.weight()) {
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if (!onQueue[w]) {
               queue.enqueue(w);
               onQueue[w] = true;
            }
         }
         if (cost++ % G.V() == 0) {
            findNegativeCycle();
            if (hasNegativeCycle()) return; // found a negative cycle
         }
   }
}

/**
* Is there a negative cycle reachable from the source vertex {@code s}?
* @return {@code true} if there is a negative cycle reachable from the
* source vertex {@code s}, and {@code false} otherwise
*/
public boolean hasNegativeCycle() {
   return cycle != null;
}

/**
* Returns a negative cycle reachable from the source vertex {@code s}, or {@code null}
* if there is no such cycle.
* @return a negative cycle reachable from the soruce vertex {@code s}
* as an iterable of edges, and {@code null} if there is no such cycle
*/
public Iterable<DirectedEdge> negativeCycle() {
   return cycle;
}

// by finding a cycle in predecessor graph
private void findNegativeCycle() {
   int V = edgeTo.length;
   EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
   for (int v = 0; v < V; v++)
         if (edgeTo[v] != null)
            spt.addEdge(edgeTo[v]);

   EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt);
   cycle = finder.cycle();
}

/**
* Returns the length of a longest path from the source vertex {@code s} to vertex {@code v}.
* @param v the destination vertex
* @return the length of a longest path from the source vertex {@code s} to vertex {@code v};
*       {@code Double.NEGATIVE_INFINITY} if no such path
* @throws UnsupportedOperationException if there is a negative cost cycle reachable
*       from the source vertex {@code s}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public double distTo(int v) {
   validateVertex(v);
   if (hasNegativeCycle())
         throw new UnsupportedOperationException("Negative cost cycle exists");
   return

1. Conversion (a) Convert the binary number 00100101 to decimal....