public void computeShortestPaths()
    {
	// Make graph gPrime, which is the same as g but with an extra
	// vertex and 0-weight edges from the extra vertex to all
	// other vertices.  In the text, the extra vertex s is v_0,
	// but here we'll make it the next available index.  The
	// Vertex objects in g will be shared with gPrime.  By making
	// s be at the next available index, every vertex in g will
	// have the same index in both g and gPrime, which is
	// necessary.

	int cardV = g.getCardV();
	WeightedAdjacencyListGraph gPrime =
	    new WeightedAdjacencyListGraph(cardV+1, true);

	Vertex[] vertices = new Vertex[cardV+1];
	Iterator vertexIter = g.vertexIterator();
	while (vertexIter.hasNext())
	    gPrime.addVertex((Vertex) vertexIter.next());
	Vertex s = new Vertex("s");
	gPrime.addVertex(s);

	vertexIter = g.vertexIterator();
	while (vertexIter.hasNext()) {
	    Vertex u = (Vertex) vertexIter.next();
	    WeightedEdgeIterator edgeIter = g.weightedEdgeIterator(u);
	    while (edgeIter.hasNext())
		gPrime.addEdge(u, (Vertex) edgeIter.next(),
			       edgeIter.getWeight());
	    
	    gPrime.addEdge(s, u, 0);
	}

	// Run the Bellman-Ford algorithm on gPrime from the source.
	BellmanFord bf = new BellmanFord(gPrime);
	bf.computeShortestPaths(s);
	if (bf.hasNoNegativeWeightCycle()) {
	    // The graph does not contain a negative-weight cycle, so
	    // we can proceed.  Compute the h values for all vertices
	    // in gPrime.
	    double[] h = new double[cardV+1];
	    for (int i = 0; i <= cardV; i++)
		h[i] = bf.getShortestPathInfo(i).getEstimate();

	    // Reweight all edges of gPrime.
	    vertexIter = gPrime.vertexIterator();
	    while (vertexIter.hasNext()) {
		Vertex u = (Vertex) vertexIter.next();
		int uIndex = u.getIndex();
		double hu = h[uIndex];

		WeightedEdgeIterator edgeIter = gPrime.weightedEdgeIterator(u);
		while (edgeIter.hasNext()) {
		    Vertex v = (Vertex) edgeIter.next();
		    double w = edgeIter.getWeight();
		    double hv = h[v.getIndex()];
		    edgeIter.setWeight(w + hu - hv);
		}
	    }

	    // Run Dijkstra's algorithm from each vertex of G in the
	    // reweighted graph.  "Un-reweight" the results.
	    Iterator uIter = g.vertexIterator();
	    while (uIter.hasNext()) {
		Vertex u = (Vertex) uIter.next();
		int uIndex = u.getIndex();
		double hu = h[uIndex];
		Dijkstra dijk = new Dijkstra(gPrime);
		dijk.computeShortestPaths(u);

		Iterator vIter = g.vertexIterator();
		while (vIter.hasNext()) {
		    Vertex v = (Vertex) vIter.next();
		    int vIndex = v.getIndex();
		    double hv = h[vIndex];

		    spInfo[uIndex][vIndex] =
			dijk.getShortestPathInfo(vIndex);
		    spInfo[uIndex][vIndex].
			setEstimate(spInfo[uIndex][vIndex].getEstimate() +
				    hv - hu);
		}
	    }	    
	}
    }