Data Structure And Algorithm

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;

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;