
Excerpts from the pseudocode are present as comments.
/** * Find the shortest path from vertex 0 to vertex N1 or state that such a path doesn't exist where the graph is represented by the adjacency matrix * dist[i][j], and the cost of passing through vertex i is cost[i] and * the money available for the trip is M. * @param M * @param dist * @param cost * @return */ public int shortestPath(int M, int[][] dist, int[] cost) { int n = cost.length; int mSize = M + 1; //Set states(i,j) as unvisited for all (i,j) boolean[][] visited = new boolean[n][]; for (int i = 0; i < n; i++) { visited[i] = new boolean[n]; } //Set memo[i][j] to Infinity for all (i,j) int[][] memo = new int[n][mSize]; for (int i = 0; i < n; i++) { memo[i] = new int[mSize]; Arrays.fill(memo[i], Integer.MAX_VALUE); } memo[0][M] = 0; int lastK = 1; int lastL = 1; while (true) { // Among all unvisited states(i,j) find the one for which memo[i][j] // is the smallest. Let this state found be (k,l). int k = 1; int l = 1; int min = Integer.MAX_VALUE; for (int i = 0; i < memo.length; i++) { for (int j = 0; j < memo[0].length; j++) { if (visited[i][j]) { continue; } if (memo[i][j] < min) { k = i; l = j; min = memo[i][j]; } } } if (k == 1) { break; } if ((k == lastK) && (l == lastL)) { break; } lastK = k; lastL = l; for (int p = 0; p < n; p++) { // neighbors have dist < inf if (dist[k][p] == Integer.MAX_VALUE) { continue; } if (visited[k][p]) { continue; } visited[k][p] = true; int c0 = l  cost[p];
//If (lS[p]>=0 AND // memo[p][lS[p]]>memo[k][l]+Dist[k][p]) // Then memo[p][lS[p]]=memo[k][l]+Dist[k][p] if ((c0 >= 0) && ((memo[p][c0] == Integer.MAX_VALUE)  (memo[p][c0] > (memo[k][l] + dist[k][p])))) { memo[p][c0] = (memo[k][l] + dist[k][p]); } } } //Find the smallest number among memo[N1][j] (for all j, 0<=j<=M); //if there are more than one such states, then take the one with greater //j. If there are no states(N1,j) with value less than Infinity  then //such a path doesn't exist. int min = Integer.MAX_VALUE; for (int j = M; j > 1; j) { if (memo[n  1][j] < min) { min = memo[n  1][j]; } } // shortest path (which is the sum of the distances) for which total cost < M return min; }
