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).
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
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
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.
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
}
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
}