Finish the ShortestPath function implementing algorithm to c

Finish the ShortestPath function implementing algorithm to compute the shortest (i.e. lowest weight) path between two vertices of an edge-weighted graph. Must implement Dijkstra’s algorithm and use a heap-based priority queue to select the nest vertex at each step (It is not necessary to store a specific minimum weight path, only to determine the total weight of such a path). A Java template has been provided containing an empty method ShortestPath, which takes a single argument consisting of a weighted adjacency matrix for an edge -weighted graph G. The expected behavior of the method is as follows:

Input: An n×n array G representing an edge-weighted graph.

Output: An integer value corresponding to the total weight of a minimum weight path from vertex 0 to vertex 1.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
import java.io.File;

public class ShortestPath{

   /* ShortestPath(G)
       Given an adjacency matrix for graph G, return the total weight
       of a minimum weight path from vertex 0 to vertex 1.
      
       If G[i][j] == 0, there is no edge between vertex i and vertex j
       If G[i][j] > 0, there is an edge between vertices i and j, and the
       value of G[i][j] gives the weight of the edge.
       No entries of G will be negative.
   */
   static int ShortestPath(int[][] G){
       int numVerts = G.length;
       int totalWeight = 0;
       /* ... Your code here ... */
      
       return totalWeight;
      
   }
   public static void main(String[] args){
       Scanner s;
       if (args.length > 0){
           try{
               s = new Scanner(new File(args[0]));
           } catch(java.io.FileNotFoundException e){
               System.out.printf(\"Unable to open %s\ \",args[0]);
               return;
           }
           System.out.printf(\"Reading input values from %s.\ \",args[0]);
       }else{
           s = new Scanner(System.in);
           System.out.printf(\"Reading input values from stdin.\ \");
       }
      
       int graphNum = 0;
       double totalTimeSeconds = 0;
      
       //Read graphs until EOF is encountered (or an error occurs)
       while(true){
           graphNum++;
           if(graphNum != 1 && !s.hasNextInt())
               break;
           System.out.printf(\"Reading graph %d\ \",graphNum);
           int n = s.nextInt();
           int[][] G = new int[n][n];
           int valuesRead = 0;
           for (int i = 0; i < n && s.hasNextInt(); i++){
               for (int j = 0; j < n && s.hasNextInt(); j++){
                   G[i][j] = s.nextInt();
                   valuesRead++;
               }
           }
           if (valuesRead < n*n){
               System.out.printf(\"Adjacency matrix for graph %d contains too few values.\ \",graphNum);
               break;
           }
           long startTime = System.currentTimeMillis();
          
           int totalWeight = ShortestPath(G);
           long endTime = System.currentTimeMillis();
           totalTimeSeconds += (endTime-startTime)/1000.0;
          
           System.out.printf(\"Graph %d: Minimum weight of a 0-1 path is %d\ \",graphNum,totalWeight);
       }
       graphNum--;
       System.out.printf(\"Processed %d graph%s.\ Average Time (seconds): %.2f\ \",graphNum,(graphNum != 1)?\"s\":\"\",(graphNum>0)?totalTimeSeconds/graphNum:0);
   }
}

Solution

import java.util.hashset;

import java.util.inputmismatchexception;

import java.util.iterator;

import java.util.scanner;

import java.util.set;

public class dijkstras_shortest_path

{

    private int          distances[];

    private set<integer> settled;

    private set<integer> unsettled;

    private int          number_of_nodes;

    private int          adjacencymatrix[][];

    public dijkstras_shortest_path(int number_of_nodes)

    {

        this.number_of_nodes = number_of_nodes;

        distances = new int[number_of_nodes + 1];

        settled = new hashset<integer>();

        unsettled = new hashset<integer>();

        adjacencymatrix = new int[number_of_nodes + 1][number_of_nodes + 1];

    }

    public void dijkstra_algorithm(int adjacency_matrix[][], int source)

    {

        int evaluationnode;

        for (int i = 1; i <= number_of_nodes; i++)

            for (int j = 1; j <= number_of_nodes; j++)

                adjacencymatrix[i][j] = adjacency_matrix[i][j];

        for (int i = 1; i <= number_of_nodes; i++)

        {

            distances[i] = integer.max_value;

        }

        unsettled.add(source);

        distances[source] = 0;

        while (!unsettled.isempty())

        {

            evaluationnode = getnodewithminimumdistancefromunsettled();

            unsettled.remove(evaluationnode);

            settled.add(evaluationnode);

            evaluateneighbours(evaluationnode);

        }

    }

    private int getnodewithminimumdistancefromunsettled()

    {

        int min;

        int node = 0;

        iterator<integer> iterator = unsettled.iterator();

        node = iterator.next();

        min = distances[node];

        for (int i = 1; i <= distances.length; i++)

        {

            if (unsettled.contains(i))

            {

                if (distances[i] <= min)

                {

                    min = distances[i];

                    node = i;

                }

            }

        }

        return node;

    }

    private void evaluateneighbours(int evaluationnode)

    {

        int edgedistance = -1;

        int newdistance = -1;

        for (int destinationnode = 1; destinationnode <= number_of_nodes; destinationnode++)

        {

            if (!settled.contains(destinationnode))

            {

                if (adjacencymatrix[evaluationnode][destinationnode] != integer.max_value)

                {

                    edgedistance = adjacencymatrix[evaluationnode][destinationnode];

                    newdistance = distances[evaluationnode] + edgedistance;

                    if (newdistance < distances[destinationnode])

                    {

                        distances[destinationnode] = newdistance;

                    }

                    unsettled.add(destinationnode);

                }

            }

        }

    }

    public static void main(string... arg)

    {

        int adjacency_matrix[][];

        int number_of_vertices;

        int source = 0, destination = 0;

        scanner scan = new scanner(system.in);

        try

        {

            system.out.println(\"enter the number of vertices\");

            number_of_vertices = scan.nextint();

            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];

            system.out.println(\"enter the weighted matrix for the graph\");

            for (int i = 1; i <= number_of_vertices; i++)

            {

                for (int j = 1; j <= number_of_vertices; j++)

                {

                    adjacency_matrix[i][j] = scan.nextint();

                    if (i == j)

                    {

                        adjacency_matrix[i][j] = 0;

                        continue;

                    }

                    if (adjacency_matrix[i][j] == 0)

                    {

                        adjacency_matrix[i][j] = integer.max_value;

                    }

                }

            }

            system.out.println(\"enter the source \");

            source = scan.nextint();

            system.out.println(\"enter the destination \");

            destination = scan.nextint();

            dijkstras_shortest_path dijkstrasalgorithm = new dijkstras_shortest_path(

                    number_of_vertices);

            dijkstrasalgorithm.dijkstra_algorithm(adjacency_matrix, source);

            system.out.println(\"the shorted path from \" + source + \" to \" + destination + \" is: \");

            for (int i = 1; i <= dijkstrasalgorithm.distances.length - 1; i++)

            {

                if (i == destination)

                    system.out.println(source + \" to \" + i + \" is \"

                            + dijkstrasalgorithm.distances[i]);

            }

        } catch (inputmismatchexception inputmismatch)

        {

            system.out.println(\"wrong input format\");

        }

        scan.close();

    }

}