LinkBack URL
About LinkBacks
Java implementing of Djikstra algorithm
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
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(); } } }
And the text file:
5
A,B-6,C-1
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
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.
Reply With Quote
