Modify the path.java program (Listing 14.2) to print a table of the minimum costs to get from any vertex to any other vertex. This exercise will require some fiddling with routines that assume the starting vertex is always A.

Listing 14.2

class DistPar // distance and parent
{ // items stored in sPath array
public int distance; // distance from start to this vertex
public int parentVert; // current parent of this vertex
public DistPar(int pv, int d) // constructor
{
distance = d;
parentVert = pv;
}
} // end class DistPar

class Vertex
{
public char label; // label (e.g. 'A')
public boolean isInTree;
public Vertex(char lab) // constructor
{
label = lab;
isInTree = false;
}
} // end class Vertex

class Graph
{
private final int MAX_VERTS = 20;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private int nTree; // number of verts in tree
private DistPar sPath[]; // array for shortest-path data
private int currentVert; // current vertex
private int startToCurrent; // distance to currentVert
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
nTree = 0;
for (int j=0; jfor(int k=0; kadjMat[j][k] = INFINITY; // to infinity
sPath = new DistPar[MAX_VERTS]; // shortest path
} // end constructor
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end, int weight)
{
adjMat[start][end] = weight; // (directed)
}
public void path() // find all shortest paths
{
int startTree = 0; // start at vertex 0
vertexList[startTree].isInTree = true;
nTree = 1; // put it in tree
// transfer row of distances from adjMat to sPath
for(int j=0; j{
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
// until all vertices are in the tree
while(nTree
{
int indexMin = getMin(); // get minimum from sPath
int minDist = sPath[indexMin].distance;
if(minDist == INFINITY) // if all infinite
{ // or in tree
System.out.println("There are unreachable vertices");
break; // sPath is complete
}
else
{ // reset currentVert
currentVert = indexMin; // to closest vert
startToCurrent = sPath[indexMin].distance;
// minimum distance from startTree is to currentVert, and is startToCurrent
}
// put current vertex in tree
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath(); // update sPath[] array
} // end while(bTreedisplayPaths(); // display sPath[] contents
nTree = 0; // clear tree
for(int j=0; jvertexList[j].isInTree = false;
} // end path()
public int getMin() // get entry from sPath
{ // with minimum distance
int minDist = INFINITY; // assume minimum
int indexMin = 0;
for(int j=1; j{ // if it's in tree and
if( !vertexList[j].isInTree && // smaller than old one
sPath[j].distance
{
minDist =sPath[j].distance;
indexMin = j; // update minimum
}
} // end for
return indexMin; // return index of minimum
} // end getMin()
public void adjust_sPath()
{ // adjust values in shortest-path array sPath
int column = 1; // skip starting vertex
while(column
{ // if this column's vertex already in tree, skip it
if( vertexList[column].isInTree )
{
column++;
continue;
} // calculate distance for one sPath entry
int currentToFringe = adjMat[currentVert][column]; // get edge from currentVert to column
int startToFringe = startToCurrent + currentToFringe; // get distance of current sPath entry
int sPathDist = sPath[column].distance;
if(startToFringe
{
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column
} // end adjust_sPath()
public void displayPaths()
{
for(int j=0; j{
System.out.print(vertexList[j].label + "="); //B=
if(sPath[j].distance == INFINITY)
System.out.print("inf"); // inf
else
System.out.print(sPath[j].distance); // 50
char parent = vertexList[sPath[j].parentVert ].label;
System.out.print("(" + parent + ") "); // (A)
}
System.out.println("");
}
} // end class Graph
class PathApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start)
theGraph.addVertex('C'); // 2
theGraph.addVertex('B'); // 1
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addEdge(0, 1, 50); // AB 50
theGraph.addEdge(0, 3, 80); // AD 80
theGraph.addEdge(1, 2, 60); // BC 60
theGraph.addEdge(1, 3, 90); // BD 90
theGraph.addEdge(2, 4, 40); // CE 40
theGraph.addEdge(3, 2, 20); // DC 20
theGraph.addEdge(3, 4, 70); // DE 70
theGraph.addEdge(4, 1, 50); // EB 50
System.out.println("Shortest paths");
theGraph.path(); // shortest paths
System.out.println();
} // end main()
} // end class PathApp