# java

Need to be done in java

Add a code in the given code// Subodh Shrestha
// CSCI308 Fall 2021 21F
// Date: 11/22/2021 Time:3:30PM
package djkstrashortestpath_shrestha;

Don't use plagiarized sources. Get Your Custom Essay on
java
Just from \$13/Page

class DsAlgorithm
{
//1.Find the shortest path for all of the given vertices:
//  We have not visited yet.
// Note:  If the vertex is marked as true, we have visited it.
//2. Update the distance value of all neighboring vertices
//   of the selected vertex
//3. Update distance[loc] if and only if it is not in the
//   PathArray, there is an shorter path from source to the vertex at loc.

public static int[] Dijkstra(int graph[][],
int s, int distanceArr[], int VNum)
{
//PathArray[j] will be true if the given vertex j
//is included in the shortest path tree from origin to j
Boolean PathArray[] = new Boolean[VNum];

// Initializing distance = INFINITE PathArray[] = false
for(int j = 0; j < VNum; j++)
{
distanceArr[j] = Integer.MAX_VALUE;
PathArray[j] = false;
}

distanceArr[s] = 0; // node to self distance is 0

for(int i = 0; i < VNum – 1; i++)
{
int minIndex = minimumDistance(distanceArr, PathArray, VNum);

PathArray[minIndex] = true;

for(int j =0; j < VNum; j++)
{
if(!PathArray[j] && graph[minIndex][j] != -1
&& distanceArr[minIndex] != Integer.MAX_VALUE
&& distanceArr[minIndex]
+ graph[minIndex][j] < distanceArr[j])
{
distanceArr[j] = distanceArr[minIndex] + graph[minIndex][j];
}
}
}
return distanceArr;
}

//Compute the min distance value between a vertex and other verticies.
public static int minimumDistance(int distance[],
Boolean PathArray[], int VNum)
{
//Let the min be an integer max value and the index begin with -1
int minimum = Integer.MAX_VALUE;
int MinimumIndex = -1;

for(int i =0; i< VNum; i++)
{
// compare values and keep the minimum
if (PathArray[i] == false && distance[i] <= minimum)
{
minimum = distance[i];
MinimumIndex = i;
}
}
return MinimumIndex;
}
}

Lab 8 – Dijkstra’s Shortest Path Extension

requested information:

Creating/Setting Up the project: Create a new project named (use your last

name): Lab8_DijkstrasShortestPath_LastName.

Create an additional java class named:

DsAlgorithm

Copy the code from the original Dijkstra’s Shortest Path Participation into the files.

Modification: Add necessary code from Lab 7 to allow the user to:

• Enter a graph

• Convert to an adjacency matrix

• And then find the shortest path between the root/source vertex at location 0 and the other vertices.

Note:

• CODE CANNOT ALL BE ADDED INTO EITHER OF THE DIJKSTRAS ALGORITHM JAVA FILES. Lab 7 code should be called in the main as needed.

• Add all error checking etc needed to keep me from braking your code.

Submit the following Grading • A png of your graph for input • pngs – 20%

• a zip of your project • working code – 70%

Adjacency Matrix Lab Create a new project: AdjacencyMatrixDynamic_LastName. Create 2 more java files:

MatrixManipulation.java and UserInterface.java. Use your Last Name as usual.

In this lab we will be creating an adjacency matrix for the following graph:

To implement the input to represent the graph, you will need to implement an arraylist that will

contain rows with vertex1, vertex2, edge. Here is a small example of what the contents should look like.

Note that the … are there because there should be more rows.

0 1 2

0 A B a

1 A E e

2 A D d

… … … …

MatrixManipulation.java In MatrixManipulation.java, we need a method to populate the matrix, you will be completing

this given the graph above. We also need a method to populate the graph, you will be completing this

given the graph above. You will be adding the code in both of these yourself.

Next, we need a method to initialize our arraylist with the character ‘0’, this will represent null

for our list.

UserInterface.java In UserInterface.java, we need a method to print the array itself.

Participation Assignment: For the in-class participation assignment, complete all of the code above. Also in the two

methods: PopulateMatrix and PopulateGraph, you need to add pseudocode for how you plan to

Submit: Zip of the project – make sure it can be run in netbeans if you want me to be able to grade it.

Grading: • Working code – 50%

• Logical and Easily Readable Pseudocode – 50%

Lab Assignment: For the completed Lab due Friday, complete the code in PopulateMatrix and PopulateGraph.

Complete the test run and add the screenshots to the screenshot document. USE THE

DEBUGGER. Add breakpoints and show the contents of the arraylists at the following parts of the code:

• After initializing matrix arraylist.

• After adding the graph information to the graph arraylist.

• After populating the matrix using the information provided in the graph.

Grading: • Working code – 75%

• Screenshot document – 30%

Dijkstra’s Shortest Path

requested information:

Creating the project: Create a new project named (use your last

name): DijkstrasShortestPath_LastName. Create

an additional java class named: DsAlgorithm

As usual, all comments seen in the code below

are required and will have points deducted for those that are missing.

DijkstrasShortestPath_LastName.java Add the variable and the print method to make sure your java file look like this:

In the main, we will initialize an adjacency matrix for the graph, then call our algorithm

to process it. Here is the adjacency matrix code so you don’t have to type it all in:

int AdjMatrix[][] = new int[][] { { -1, 3, -1, -1, -1, -1, -1, 7, -1 }, { 3, -1, 7, -1, -1, -1, -1, 10, 4 }, { -1, 7, -1, 6, -1, 2, -1, -1, 1 }, { -1, -1, 6, -1, 8, 13, -1, -1, 3 }, { -1, -1, -1, 8, -1, 9, -1, -1, -1 }, { -1, -1, 2, 13, 9, -1, 4, -1, 5 }, { -1, -1, -1, -1, -1, 4, -1, 2, 5 }, { 7, 10, -1, -1, -1, -1, 2, -1, 6 }, { -1, 4, 1, 3, -1, 5, 5, 6, -1 } };

For printDistances, we will print out the shortest distances between our origin and our vertices. Above the first println, add another println with the following: “Welcome to ” + yourname + “’s program.”

The output will look similar to this, with your string at the top:

DsAlgorithm.java Add the following in the DsAlgorithm class:

Inside our Dijkstra method, add the following: (we will add code in the for loop next)

Here is the code for the for loop:

In the minDistance method, we compute the difference. Add the following code:

Run the code and make sure it works.

Submit the following: • a png of your results

• a zip of your project