So in my code, I'm trying to find the shortest path from 0 to 1. I get the graphs from an adjacency matrix. So what I do is I start at the first row (or the 0th row) and traverse through the row and relax the vertices in a matrix called N. I then find the smallest edge coming out of whatever vertices I have stored in my vertex storage and then continue adding vertices and relaxing the edges. So then I have two main arrays called N (where I store the weights of the shortest paths) and edgeStorage. Here's what it looks like:

static int ShortestPath(int[][] G){ int numVerts = G.length; int totalWeight = 0; int minWeight; int count = 1; int k = 0; int l = 0; int next = 1; int i = 0; int[] N = new int[numVerts]; int[] edgeStorage = new int[numVerts]; Arrays.fill(N, 2147483647); //2147483647 is my infinity to represent vertices that haven't yet been relaxed N[0] = 0; while (count != numVerts){ for (int j = 0; j < numVerts; j++){ if ((G[i][j] != 0) && (N[i] + G[i][j] < N[j])){ N[j] = N[i] + G[i][j]; } } minWeight = 2147483647; for (int p = 0; p < count; p++){ //find min edge weight for vertices in storage i = edgeStorage[p]; for (int j = 0; j < numVerts; j++){ if ((G[i][j] != 0) && (G[i][j] < minWeight)){ minWeight = G[i][j]; k = j; l = i; } } } G[l][k] = 0; //remove edge since we don't need it anymore G[k][l] = 0; edgeStorage[next] = k; //store vertex location in array i = k; count++; next++; } totalWeight = N[1]; return totalWeight; }

The problem is this code works for some graphs but for others it gives me a weight that's bigger than it's supposed to be. I have no idea why it gives me the wrong weight for some graphs but the right weight for others. So does anyone know what's wrong with my code?