PLease solve this problem using the main method provided and make sure to get the same output i posted. When done please post the entire program and the whole output you get. Thank you very much.

14.3

Implement Floyds algorithm. You can start with the path.java program (Listing 14.2) and modify it as appropriate. For instance, you can delete all the shortestpath code. Keep the infinity representation for unreachable vertices. By doing this, you will avoid the need to check for 0 when comparing an existing cost with a newly derived cost. The costs on all possible routes will be less than infinity. You should be able to enter graphs of arbitrary complexity into main().

Listing 14.2

// path.java // demonstrates shortest path with weighted, directed graphs // to run this program: C>java PathApp //////////////////////////////////////////////////////////////// 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]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; nTree = 0; 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 < 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(nTree

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 columns vertex already in tree, skip it if( vertexList[column].isInTree ) { column++; continue; } // calculate distance for one sPath entry // get edge from currentVert to column int currentToFringe = adjMat[currentVert][column]; // add distance from start int startToFringe = startToCurrent + currentToFringe; // get distance of current sPath entry int sPathDist = sPath[column].distance; // compare distance from start with sPath entry if(startToFringe < sPathDist) // if shorter, { // update sPath sPath[column].parentVert = currentVert; sPath[column].distance = startToFringe; } column++; } // end while(column < nVerts) } // end adjust_sPath() // ------------------------------------------------------------- public void displayPaths()

{ for(int j=0; j

You MUST use this main method. (see also p.708 Data structures and algorithms in java 2nd edition)

public static void main(String[] args) throws IOException

{

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

System.out.println("Adjacency Matrix:");

theGraph.adjMatDisplay();

System.out.println();

theGraph.floyd(); // execute Floyd's Algorithm

System.out.println();

} // end main()

The output MUST look like this:

Adjacency Matrix:

A B C D E

====================

A --- 50 --- 80 ---

B --- --- 60 90 ---

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 --- --- ---

After y=1, x=2, z=0

A B C D E

====================

A --- 50 110 80 ---

B --- --- 60 90 ---

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 --- --- ---

Press Enter to continue:

After y=1, x=2, z=4

A B C D E

====================

A --- 50 110 80 ---

B --- --- 60 90 ---

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 110 --- ---

Press Enter to continue:

After y=1, x=3, z=4

A B C D E

====================

A --- 50 110 80 ---

B --- --- 60 90 ---

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 110 140 ---

Press Enter to continue:

After y=2, x=4, z=0

A B C D E

====================

A --- 50 110 80 150

B --- --- 60 90 ---

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 110 140 ---

Press Enter to continue:

After y=2, x=4, z=1

A B C D E

====================

A --- 50 110 80 150

B --- --- 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 70

E --- 50 110 140 ---

Press Enter to continue:

After y=2, x=4, z=3

A B C D E

====================

A --- 50 110 80 150

B --- --- 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 ---

Press Enter to continue:

After y=2, x=4, z=4

A B C D E

====================

A --- 50 110 80 150

B --- --- 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=3, x=2, z=0

A B C D E

====================

A --- 50 100 80 150

B --- --- 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=3, x=4, z=0

A B C D E

====================

A --- 50 100 80 140

B --- --- 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=1, z=1

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- --- --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=1, z=2

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- 90 --- --- 40

D --- --- 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=1, z=3

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- 90 --- --- 40

D --- 110 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=2, z=2

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- 90 150 --- 40

D --- 110 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=3, z=2

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- 90 150 180 40

D --- 110 20 --- 60

E --- 50 110 140 150

Press Enter to continue:

After y=4, x=3, z=3

A B C D E

====================

A --- 50 100 80 140

B --- 150 60 90 100

C --- 90 150 180 40

D --- 110 20 200 60

E --- 50 110 140 150

Press Enter to continue: