#The ProblemThe problem is: (from from Herehere) :
#TheThe page at Wikipedia said:
#And Here is my implementation: final int mEdge = 80; final int mInfinity = Integer.MAX_VALUE / 4; String mText = getText(83); int[][] mDistances = new int[mEdge][mEdge]; int[][] mMatrix = get2DArray(mText, mEdge); int mSourceX = 0; // 1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. for (int i = 0; i < mEdge; i++) { for (int j = 0; j < mEdge; j++) { mDistances[i][j] = mInfinity; } } mDistances[mSourceX][0] = 0; boolean[][] mVisited = new boolean[mEdge][mEdge]; // 2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set. int mCurrentX = mSourceX, mCurrentY = 0; mVisited[mSourceX][0] = true; List mUnvisitedList = new ArrayList(); for (int i = 0; i < mEdge; i++) { for (int j = 0; j < mEdge; j++) { if (!mVisited[i][j]) { mUnvisitedList.add(i + "." + j); } } } do { // 3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated // tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a // distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B // was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. if (mCurrentX < mEdge - 1) { if (!mVisited[mCurrentX + 1][mCurrentY]) { mDistances[mCurrentX + 1][mCurrentY] = Math.min(mDistances[mCurrentX + 1][mCurrentY], mMatrix[mCurrentX + 1][mCurrentY] + mDistances[mCurrentX][mCurrentY]); } } if (mCurrentX > 0) { if (!mVisited[mCurrentX - 1][mCurrentY]) { mDistances[mCurrentX - 1][mCurrentY] = Math.min(mDistances[mCurrentX - 1][mCurrentY], mMatrix[mCurrentX - 1][mCurrentY] + mDistances[mCurrentX][mCurrentY]); } } if (mCurrentY < mEdge - 1) { if (!mVisited[mCurrentX][mCurrentY + 1]) { mDistances[mCurrentX][mCurrentY + 1] = Math.min(mDistances[mCurrentX][mCurrentY + 1], mMatrix[mCurrentX][mCurrentY + 1] + mDistances[mCurrentX][mCurrentY]); } } if (mCurrentY > 0) { if (!mVisited[mCurrentX][mCurrentY - 1]) { mDistances[mCurrentX][mCurrentY - 1] = Math.min(mDistances[mCurrentX][mCurrentY - 1], mMatrix[mCurrentX][mCurrentY - 1] + mDistances[mCurrentX][mCurrentY]); } } // 4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the // unvisited set. A visited node will never be checked again. mVisited[mCurrentX][mCurrentY] = true; mUnvisitedList.remove(mCurrentX + "." + mCurrentY); // 5. If the destination node has been marked visited (when planning a route between two specific nodes), then stop. The algorithm has // finished. if (mVisited[mEdge - 1][mEdge - 1] == true) { return mDistances[mEdge - 1][mEdge - 1] + mMatrix[0][0]; } else { // 6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and // go back to step 3. int mMinDistance = mInfinity; int[] mNextCurrentNode = stringArraytoIntArray(mUnvisitedList.get(0).split("\.")); for (String mUnvisitedNode : mUnvisitedList) { String[] mStringArrayCoordinates = mUnvisitedNode.split("\."); int[] mIntArrayCoordinates = stringArraytoIntArray(mStringArrayCoordinates); if (mDistances[mIntArrayCoordinates[0]][mIntArrayCoordinates1] < mMinDistance && !mVisited[mIntArrayCoordinates[0]][mIntArrayCoordinates1]) { mNextCurrentNode = mIntArrayCoordinates; mMinDistance = mDistances[mIntArrayCoordinates[0]][mIntArrayCoordinates1]; }
final int mEdge = 80;
final int mInfinity = Integer.MAX_VALUE / 4;
String mText = getText(83);
int[][] mDistances = new int[mEdge][mEdge];
int[][] mMatrix = get2DArray(mText, mEdge);
int mSourceX = 0;
// 1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
for (int i = 0; i < mEdge; i++) {
for (int j = 0; j < mEdge; j++) {
mDistances[i][j] = mInfinity;
}
}
mDistances[mSourceX][0] = 0;
boolean[][] mVisited = new boolean[mEdge][mEdge];
// 2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
int mCurrentX = mSourceX, mCurrentY = 0;
mVisited[mSourceX][0] = true;
List<String> mUnvisitedList = new ArrayList<String>();
for (int i = 0; i < mEdge; i++) {
for (int j = 0; j < mEdge; j++) {
if (!mVisited[i][j]) {
mUnvisitedList.add(i + "." + j);
}
}
}
do {
// 3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated
// tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a
// distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B
// was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
if (mCurrentX < mEdge - 1) {
if (!mVisited[mCurrentX + 1][mCurrentY]) {
mDistances[mCurrentX + 1][mCurrentY] = Math.min(mDistances[mCurrentX + 1][mCurrentY], mMatrix[mCurrentX + 1][mCurrentY]
+ mDistances[mCurrentX][mCurrentY]);
}
}
if (mCurrentX > 0) {
if (!mVisited[mCurrentX - 1][mCurrentY]) {
mDistances[mCurrentX - 1][mCurrentY] = Math.min(mDistances[mCurrentX - 1][mCurrentY], mMatrix[mCurrentX - 1][mCurrentY]
+ mDistances[mCurrentX][mCurrentY]);
}
}
if (mCurrentY < mEdge - 1) {
if (!mVisited[mCurrentX][mCurrentY + 1]) {
mDistances[mCurrentX][mCurrentY + 1] = Math.min(mDistances[mCurrentX][mCurrentY + 1], mMatrix[mCurrentX][mCurrentY + 1]
+ mDistances[mCurrentX][mCurrentY]);
}
}
if (mCurrentY > 0) {
if (!mVisited[mCurrentX][mCurrentY - 1]) {
mDistances[mCurrentX][mCurrentY - 1] = Math.min(mDistances[mCurrentX][mCurrentY - 1], mMatrix[mCurrentX][mCurrentY - 1]
+ mDistances[mCurrentX][mCurrentY]);
}
}
// 4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the
// unvisited set. A visited node will never be checked again.
mVisited[mCurrentX][mCurrentY] = true;
mUnvisitedList.remove(mCurrentX + "." + mCurrentY);
// 5. If the destination node has been marked visited (when planning a route between two specific nodes), then stop. The algorithm has
// finished.
if (mVisited[mEdge - 1][mEdge - 1] == true) {
return mDistances[mEdge - 1][mEdge - 1] + mMatrix[0][0];
} else {
// 6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and
// go back to step 3.
int mMinDistance = mInfinity;
int[] mNextCurrentNode = stringArraytoIntArray(mUnvisitedList.get(0).split("\\."));
for (String mUnvisitedNode : mUnvisitedList) {
String[] mStringArrayCoordinates = mUnvisitedNode.split("\\.");
int[] mIntArrayCoordinates = stringArraytoIntArray(mStringArrayCoordinates);
if (mDistances[mIntArrayCoordinates[0]][mIntArrayCoordinates[1]] < mMinDistance
&& !mVisited[mIntArrayCoordinates[0]][mIntArrayCoordinates[1]]) {
mNextCurrentNode = mIntArrayCoordinates;
mMinDistance = mDistances[mIntArrayCoordinates[0]][mIntArrayCoordinates[1]];
}
mCurrentX = mNextCurrentNode[0];
mCurrentY = mNextCurrentNode[1];
}
}
} while (true);
#II am wishing to have a review on:
- Speed (currently over 30 seconds on my hardware)
- An other improvements possible or things you notice.
#P.S. Other useful methods used in above implementation are here.
