The problem is from here:
The page at Wikipedia said:
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
- 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.
- 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.
- If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
- 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.
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<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);
I am wishing to have a review on:
- Speed (currently over 30 seconds on my hardware)
- An other improvements possible or things you notice
Other useful methods used above are here.