public class Dijkstra_Algo {
private static void dijkstra(int [][] adjacencyMatrix) {
int v = adjacencyMatrix.length; // to get total vertices
boolean visited[] = new boolean[v]; // to mark a vertex as visited
int distance[] = new int[v]; // distance of every vertex
// initially we are setting all the distance to infinty
distance[0] = 0;
for(int i = 0; i < v; i++) {
distance[i] = Integer.MAX_VALUE; // setting distance of vertx to infinity from src except for the first vertex
}
// Now we are going to work on every vertex
for(int i = 0; i < v - 1; i++) {
// here we want the vertex which has min distance or weight
// find minimum distance
int minVertex = findMinVertex(distance, visited);//here we are giving array of distance along with array of visited beac
visited[minVertex] = true;
// Explore all neighbors as we are using adjacency matrix
for(int j = 0; j < v; j++) {
// here we use if condition to check that the vertex is neighbor or not and it has to not visited then we are going to calculate distance of every vertex
if(adjacencyMatrix[minVertex][j] != 0 && !visited[j] && distance[minVertex] != Integer.MAX_VALUE) {
int newDist = distance[minVertex] + adjacencyMatrix[minVertex][j];
if(newDist < distance[j]) {
distance[j] = newDist;
}
}
}
}
// here we are going to print
for(int i = 0; i < v; i++) {
System.out.println(i +" " + distance[i]);
}
}
//
private static int findMinVertex(int[] distance, boolean visited[]) {
int minVertex = -1;
for(int i = 0; i < distance.length; i++) {
if(!visited[i] && (minVertex ==-1 || distance[i] < distance[minVertex])) {
minVertex = -1;
}
}
return minVertex;
}
public static void main(String[] args) throws ArrayIndexOutOfBoundsException {
Scanner s = new Scanner(System.in);
int v = s.nextInt();
int e = s.nextInt();
int adjacencyMatrix[][] = new int[v][v];
for(int i=0; i<e; i ++){
int v1 = s.nextInt();
int v2 = s.nextInt();
int weight = s.nextInt();
adjacencyMatrix[v1][v2] = weight;
adjacencyMatrix[v2][v1] = weight;
}
dijkstra(adjacencyMatrix);
s.close();
}
}
error that i am getting after giving for this input input -
5 7
0 1 4
0 2 8
1 3 5
1 2 2
2 3 5
2 4 9
3 4 4
error -
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
at com.company.Dijkstra_Algo.dijkstra(Dijkstra_Algo.java:24)
at com.company.Dijkstra_Algo.main(Dijkstra_Algo.java:71)