Java algorithm implementation showing error

Question

I am trying to implement java for Dijkstra algorithm (Shortest Path Tree). The graph node are being read from a text file which contains string|(vertex) and int (weight) between vertexes. But when running the program it thrown me an error

Exception in thread "main" java.util.InputMismatchException

>at java.util.Scanner.throwFor(Unknown Source)

>at java.util.Scanner.next(Unknown Source)

>at java.util.Scanner.nextInt(Unknown Source)

>at java.util.Scanner.nextInt(Unknown Source)

>at ASD4_dijkstra.main(ASD4_dijkstra.java:94)

This is the code of java

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;



public class ASD4_dijkstra {



    // A utility function to find the vertex with minimum distance value,

    // from the set of vertices not yet included in shortest path tree

    static final int V = 5;

    int minDistance(int dist[], Boolean sptSet[]) {

        // Initialize min value

        int min = Integer.MAX_VALUE, min_index = -1;



        for (int v = 0; v < V; v++)

            if (sptSet[v] == false && dist[v] <= min) {

                min = dist[v];

                min_index = v;

            }



        return min_index;

    }



    // A utility function to print the constructed distance array

    void printSolution(int dist[], int n) {

        System.out.println("Distance from starting vertex");

        for (int i = 0; i < V; i++)

            System.out.println(i + " \t\t " + dist[i]);

    }



    // Funtion that implements Dijkstra's single source shortest path

    // algorithm for a graph represented using adjacency matrix

    // representation

    void dijkstra(int graph[][], int src) {

        int dist[] = new int[V]; // The output array. dist[i] will hold

        // the shortest distance from src to i



        // sptSet[i] will true if vertex i is included in shortest

        // path tree or shortest distance from src to i is finalized

        Boolean sptSet[] = new Boolean[V];



        // Initialize all distances as INFINITE and stpSet[] as false

        for (int i = 0; i < V; i++) {

            dist[i] = Integer.MAX_VALUE;

            sptSet[i] = false;

        }



        // Distance of source vertex from itself is always 0

        dist[src] = 0;



        // Find shortest path for all vertices

        for (int count = 0; count < V - 1; count++) {

            // Pick the minimum distance vertex from the set of vertices

            // not yet processed. u is always equal to src in first

            // iteration.

            int u = minDistance(dist, sptSet);



            // Mark the picked vertex as processed

            sptSet[u] = true;



            // Update dist value of the adjacent vertices of the

            // picked vertex.

            for (int v = 0; v < V; v++)



                // Update dist[v] only if is not in sptSet, there is an

                // edge from u to v, and total weight of path from src to

                // v through u is smaller than current value of dist[v]

                if (!sptSet[v] && graph[u][v] != 0 &&

                    dist[u] != Integer.MAX_VALUE &&

                    dist[u] + graph[u][v] < dist[v])

                    dist[v] = dist[u] + graph[u][v];

        }



        // print the constructed distance array

        printSolution(dist, V);

    }



    // Driver method

    public static void main(String[] args) {

        File file = new File("C:\\Users\\leotr\\Downloads\\alg4.txt");

        try {



            Scanner sc = new Scanner(file);

            int graph[][] = new int[5][5];

            for (int i = 0; i < 5; i++) {

                for (int j = 0; j < 5; j++) {

                    graph[i][j] = sc.nextInt();

                }

            }

            sc.close();

        } catch (FileNotFoundException e) {

            e.printStackTrace();

        }

    }



}

I searched in google , and found the cause of error. It because the textfile contain int and string, and in the code its declared to get only int, but can't figure how to change the code, to make work.

EDIT:

text file

    5// number of nodes into graph

    A,B-6,C-1//name of node and connection with other nodes , and her weight

    B,A-6,C-3,D-7,E-2

    C,A-1,B-3,D-1

    D,B-7,C-1,E-2

    E,B-2,D-2 

First line of file mean the number of nodes in the graph, and other lines represent the names of node and connection with other nodes, and connection weight.

For example A,B-12,C-5 means A connect with B, and the weight Of this connection is 12, node a connect with node c and the weight is 5.

My question is what to change in the loop(main void), to make the program work (read the text file, and calculate the shortest path tree)

Answer 1

You're using nextInt() on input which does not contain only integers, but other characters like commas and letters. You need to separate the integers and the text.

The way I would go about doing this is with String.charAt();

You need to determine where each number begins. For example, assuming that each node can only be called a name that is 1 character long, you know that there is an integer, specifically the integer you're looking for (since the dash indicated a negative), on the 5th, 9th, 13th, and 17th positions.

So to extract those specific integers as characters, you can use String.charAt() and plug in the indexes of the numbers, which are the multiples of 4 (since the position in the string are the multiples of 4 + 1 and strings start at index 0).

To get the integer itself, you would use String.valueOf() or Integer.parseInt() where you can just plug in the character at the indexes.

So to summarize, the way I would do this is as follows:

    int nodes = Integer.parseInt(sc.nextLine()); //This takes the first line, the number of nodes and converts it to an integer.
    for(int i = 0; i < nodes; i++){ //This loop will go through each line

        String line = sc.nextLine(); //This extracts each individual line into a string

        for(int j = 4; j < line.length; i+=4){ 
            //This goes through each individual line, through the indexes that are multiples of 4, which we established are the integers you're looking for above.

            String.valueOf(line.charAt(j)); //This returns each integer inside each line in the input text file.

            Integer.parseInt(line.charAt(j)); //This line does the same thing as above.
            /*I'm not sure how to implement this into your algorithm, but I've done the integer extracting bit. 
             * Either of the two lines of code above will give you the integers you're looking for.
            */
        }

    }

To be clear, the code I gave you only extracts the integers you're looking for, it doesn't actually put them where you need them. I hope this was helpful.