JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Upper-Intermediate: I am having a hard time implementing the pseudo-code in java | Reply
Will someone please implement the Upper-Intermediate pseudo-code in Java? Thanks.
Re: Upper-Intermediate: I am having a hard time implementing the pseudo-code in java (response to post by kasavbere) | Reply
Excerpts from the pseudocode are present as comments.


/**
* Find the shortest path from vertex 0 to vertex N-1 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 (l-S[p]>=0 AND
// memo[p][l-S[p]]>memo[k][l]+Dist[k][p])
// Then memo[p][l-S[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[N-1][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(N-1,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;
}
Re: Upper-Intermediate: I am having a hard time implementing the pseudo-code in java (response to post by nkin) | Reply
Isn't the upper intermediate problem same as intermediate problem?
It is just that instead of maximizing the number of apples that can be collected, we are just trying to minimize the cost at each vertex?
RSS