Dijkstra's Algorithm in Project Euler# 83: Path sum: four ways

Question

The problem is from here:

The page at Wikipedia said:

1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
2. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
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.
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.
5. 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.
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.

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.

Answer 1

Okay, first off. Please post the whole code, preferably in a runnable example.

There are many things you can do to improve performance.

Prefer Contiguous Arrays

Defining a 2D array as int[][] is not optimal as it is "arrays inside of arrays" (i.e. the outer array is an array of pointers to the inner rows/columns) meaning that you will get an extra indirection and possibly a cache miss on each element access. You should create one contiguous 1D array and index into it based on x,y. Like this:

int[][] slow = new int[width][height];
int[] fast = new int[width*height];

slow[x][y] == fast[x + y * width];

This also goes for your visited list.

For the love of ${DEITY}, don't encode coordinates into strings

Instead of String pos = x+"."+y; simply use Point pos = new Point(x,y). Much faster, especially since you don't have to parse out the x and y values when you use it.

Use the correct data structure and algorithm for unvisited nodes

You are storing your unvisited nodes in a list and doing a linear search through it for the next unvisited node. This is what is ruining your algorithm performance of Dijkstra, going from O(E + VlogV) to O(E + V^2) and why it takes 30 seconds for your machine.

First off you only need to store the currently accessible, unvisited nodes. This alone would significantly speed up your search for the unvisited node with smallest cost. You can do this by adding the neighbours of the current node to the unvisited nodes set only if they don't already exist in the set. (You can keep an additional matrix with nodes that have been added or you can query the set if it contains the node provided you have O(logn) lookup).

Next as you will be taking the smallest element as the next node, it makes sense to use an ordered data structure such as a heap or also known as a PriorityQueue in Java. Note that if you do use the priority queue you need to remove and re-add elements as you change their cost so that they get re-sorted in the queue.

Use an Object Oriented Solution

You have many matrixes (arrays) of the same size that represent different properties of each node. It makes sense to just consolidate these arrays into one array of nodes where each node has properties.

Like this:

class DijkstraNode{
    double value;
    double bestCostThisFar = Double.PositiveInfinity();
    boolean visited = false;
    boolean addedToUnvisited = false;
    int x;
    int y;
}

DijkstraNode graph[] = new DijkstraNode[mEdge*mEdge];

PriorityQueue<DijkstraNode> unvisited = new PriorityQueue<>(mEdge*mEdge, comparator);

Where you implement a suitable Comparator.

This means that your data will have a much better cache coherency as the data you will be using will fit on the same cache line.