$2.$ In this project, we're not going to implement the general algorithm; instead, we're going to use it to map out the distances between spaces on a grid.

Your file will be named dijkstra$\_$on$\_$grid.py $.$

$2\mathrm{.}1$ Required Class: DijkstraNode

You are required to use the class DijkstraNode,

class DijkstraNode:

def $\_\_$init$\_\_($self$)$:

self.$\_$dist $=$ None # not reached yet, treat as infinite distance

self.$\_$done $=$ False

def is$\_$done$($self$)$:

return self.$\_$done

def is$\_$reached$($self$)$:

return self.$\_$dist is not None

def get$\_$dist$($self$)$:

assert self.$\_$dist is not None

return self.$\_$dist

def update$\_$dist$($self$,$ new$\_$dist$)$:

assert new$\_$dist $>=0$

assert not self.$\_$done

assert self.$\_$dist is None or new$\_$dist $<$ self.$\_$dist

self.$\_$dist $=$ new$\_$dist

def set$\_$done$($self$)$:

assert not self.$\_$done

self.$\_$done $=$ True

$3.$ Map Format

Our input files will be maps, that give a grid of spaces. Spaces that are usable are marked with hash signs, and spaces that cannot are empty spaces in the file.

$4.$ Program Input

Your first input will the name of the maze file $($see the testcases for the prompt$).$ Second, you will then read two inputs: the $($x$,$y$)$ location of the start of the search. Third, you will read a command: it will be either "animate" or "fill". The animate command will be useful to help you debug your implementation; it shows every single step of the algorithm, along with debug information. The fill command exists to help you get partial credit: if your animate command doesn't work entirely, you still can get some credit with the fill command.

$5.$ Printing the Map $($when Filled$)$

When you print out the map, you will print out the distances. That is$,$ for each point on the map, you will print out how many steps it took to get from the starting point to that location.

$6.$ Printing the Map $($when Animating$)$

When you are in the middle of an animation, you$$ll print the map using the

same basic format $-$ but with some new notations.

$7.$ The TODO List

you must maintain a "TODO list" $($often described as a queue$)$ of points. These are points which you have reached, somewhere in the graph $-$ meaning that you've found at least one path to get to them $-$ but you are not yet $100\%$ certain that you've found the best path.

The TODO list is always sorted $-$ with the nodes with the smallest distance coming first $-$ and each entry must have some sort of pointer which tells you which node it's talking about. In our problem, we this is extremely simple: each node in the TODO list is a tuple

$($dist$,$ x$,$ y$)$

that tells you the distance to the node, and its coordinates in the grid.

$7\mathrm{.}1$ Simple Hacks, Not Realistic

Our program is using a couple simplifications about the TODO list, which are not realistic. First, as we just noted, we use the $($x$,$ y$)$ location to indicate each node in the TODO list. If the data is a graph, we don't have a grid $-$ meaning that each element of the TODO list probably would have a reference to an object $($something similar to the DijkstraNode that I've given you$)$ to store per$-$node information. So our implementation is simple but unrealistic.

Second, I$\text{'}$m assuming that most students will simply store the TODO list as an array, and re$-$sort it every time that they change it$.$ This is perfectly OK but it's not realistic, since sorting the array takes O$($n lg n$)$ time.

Some of the more advanced students might iterate through the array, and insert$/$delete individual elements. This is better than sorting, but it still takes O$($n$)$ time $-$ which is still slow by Dijkstra's Algorithm standards. In the Real World, we have even faster data structures $-$ but they are too complex for $120.$

Feel free to use the hackish design!

$7\mathrm{.}2$ Printing the TODO List

If you are animating the algorithm, you will print the map first, and then print the TODO list afterward, on every step.