Assignment #4: Shortest Paths

The input will consist of files containing matrices of non-negative integers. There will always be a 0 in the upper left and a 0 in the lower right. The assignment is to solve two separate problems on this data using a shortest path algorithm (or variant).

PART #1

You must find the shortest path from the upper left to the lower right, in which the cost of the path is measured by the sum of the values in the cells on the path, and in which a valid step in the path is to any adjacent (at most eight) cell. For instance, in the matrix below:

 0 44 15 82
61 17 28 94
11 54 10 28
12 43 77 62
40 13 14  0

the solution is a path of cost of 67 as follows:

(0,0) cell is 0
(1,1) cell is 17
(2,0) cell is 11
(3,0) cell is 12
(4,1) cell is 13
(4,2) cell is 14
(4,3) cell is 0
Total cost is 67

PART #2

Now imagine that each cell represents a weight limit and you need get from the upper left to the lower right (those squares have no weight limit). Find the path that allows you to transport the most weight.

For the matrix above, the solution is a path that allows weight 54 as follows:

(0,0) cell is START
(1,0) cell is 61
(2,1) cell is 54
(3,2) cell is 77
(4,3) cell is END
All cells support 54

DATA FILES

I will provide a set of data files, including some large files. If there are more than 20 cells on the path, print the first ten, then a line with ... and then the last ten, along with the total cost.  Otherwise, print the entire path.

These are both shortest path problems that can be solved with Dijkstra's algorithm and you should use a reasonable implementation that includes a priority queue to obtain an O(N log N) running time (see below). In both cases, the problem is simpler than Dijkstra's algorithm due to the structure of the "graph". In particular once a cost of a vertex is changed from the initial value (infinity in part 1, or 0 in part 2), it is never changed again.

ALGORITHM SKETCHES

Part #1:

initialize all distances to INFINITY, except start distance is 0
pq is a priority queue that returns MINIMUM
pq.add( start square );

while( !pq.isEmpty( ) )
{
    v = pq.remove( );

    for each square w adjacent to v
        if w's distance is INFINITY
            set w's distance to v's distance + w's square cost, and add w to priority queue
}

Part #2:

initialize all weights to 0, except adjust start and end square to INFINITY
pq is a priority queue that returns MAXIMUM
pq.add( start square );

while( !pq.isEmpty( ) )
{
    v = pq.remove( );

    for each square adjacent to v
        if w's weight is 0
            set w's weight to MIN( v's weight, w's square cost ), and add w to priority queue
}