JAVA PROGRAMMING QUESTION!!!!!!!!!!!!!!!!!!!!!!!!!!!! Modify the path.java progr
ID: 3570448 • Letter: J
Question
JAVA PROGRAMMING QUESTION!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Modify the path.java program 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. You can create such a table by running the path.java program using each vertex in turn as the starting vertex.
Here are the four classes for the exsisting program to modify:
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 PathAp
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; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix
adjMat[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<nVerts; j++)
{
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
// until all vertices are in the tree
while(nTree < nVerts)
{
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(bTree<nVerts)
displayPaths(); // display sPath[] contents
nTree = 0; // clear tree
for(int j=0; j<nVerts; j++)
vertexList[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<nVerts; j++) // for each vertex,
{ // if it's in tree and
if( !vertexList[j].isInTree && // smaller than old one
sPath[j].distance < minDist )
{
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 < nVerts) // go across columns
{ // 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 < sPathDist) // if shorter, update path
{
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
} // end adjust_sPath()
public void displayPaths()
{
for(int j=0; j<nVerts; j++) // display contents of sPath[]
{
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
Explanation / Answer
class PathApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
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
theGraph.addEdge(3, 0, 90); // EA 90
theGraph.addEdge(1, 0, 20); // BA 20
theGraph.addEdge(4, 3, 10); // ED 10
theGraph.addEdge(2, 0, 5); // CA 5
System.out.println("Shortest paths");
theGraph.path('A','E'); // shortest paths
System.out.println();
} // end main()
} // end class PathAp
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; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix
adjMat[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)
}
private int getVertex(char vert){
if (vert=='X') return -2;
for(int j=0;j<nVerts;j++)
if (vertexList[j].label==vert) return j;
return -1;
}
public void path(char startv,char endv) // find all shortest paths
{
int startTree=getVertex(startv);
if (startTree==-2) startTree=0; // start at vertex 0 if 'X'
vertexList[startTree].isInTree = true;
nTree = 1; // put it in tree
// transfer row of distances from adjMat to sPath
for(int j=0; j<nVerts; j++)
{
int tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
// until all vertices are in the tree
while(nTree < nVerts)
{
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(bTree<nVerts)
int endVer=getVertex(endv);
if (endVer==-2)
displayPaths(); // display sPath[] contents, means all
else
displayPaths(startTree,endVer); // display till end vertex
nTree = 0; // clear tree
for(int j=0; j<nVerts; j++)
vertexList[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<nVerts; j++) // for each vertex,
{ // if it's in tree and
if( !vertexList[j].isInTree && // smaller than old one
sPath[j].distance < minDist )
{
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 < nVerts) // go across columns
{ // 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 < sPathDist) // if shorter, update path
{
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
} // end adjust_sPath()
public void displayPaths()
{
for(int j=0; j<nVerts; j++) // display contents of sPath[]
{
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("");
}
public void displayPaths(int start,int end)
{
int maxDistance=sPath[end].distance;
int dist=0;
for(int i=start;i<=end;i++){
char node=vertexList[i].label;
char parent=vertexList[sPath[i].parentVert ].label;
if (((node!=parent) && (sPath[i].distance != INFINITY))){
dist+=Integer.valueOf(sPath[i].distance);
if ((dist<maxDistance)||(i==end)){
System.out.print(" ("+parent+","+node+")"+ " = "); //B=
System.out.print(sPath[i].distance); // 50
}
}
}
System.out.println("");
}
} // end class Graph
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.