All times given are real time (not cpu time) on an entirely unloaded
computer.
The same computer was used as for the word-search tournament.
All programs were tested on 50,000 short-distance searches. A time limit of five minutes was given.
You can look up your own running time (in ms / query) on whiteboard; it is listed as the "grade" for "assignment" MRshort. A running time of 6 indicates that your program either exceeded the time limit or gave at least one incorrect answer.
Number of programs giving correct answers for all queries within time limit: 22
Average time (ms) per query (among this group): 2.68
Median time per query: 2.76
All programs were tested on 1,000 long-distance searches. A time limit of five minutes was given.
You can look up your own running time (in ms / query) on whiteboard; it is listed as the "grade" for "assignment" MRlong. A running time of 300 indicates that your program either exceeded the time limit or gave at least one incorrect answer.
Number of programs giving correct answers for all queries within time limit: 27
Average time (ms) per query (among this group): 81.57
Median time per query: 66.22
I made three major modifications to the dijkstra algorithm. The first was to break the loop as soon as the destination vertex is reached rather than continuing until all vertices have been reached. This necessitated storing which vertices were affected and then resetting them for the next query. In order to do this in a somewhat efficient manner I kept an array of integers - one for each vertex. Each entry touched[v] stored the number of the vertex touched immediately before vertex v was processed. This made it simple to step back through the array clearing out all the affected vertices. The second modification was to use and A* heuristic. Here all I did was add the euclidean distance from the point to the destination to the distance value used by the priority queue. This meant that the queue tended to return vertices closer to the destination and more likely to provide a shortest path. I also had each vertex cache its distance from the destination. Since that calculation requires a square root caching it ought to provide some speed benefit.Lastly I realized that the priority queue operations are O(log(n)). This means that storing fewer items in the priority queue would give better times. So rather than putting the entire graph in the queue I just added the neighbors of the vertices that had been considered.
My idea in the Dijkstra algorithm was to remember the nodes that were visited and modified by the Dijkstra algorithm. Then at the end of each search instead of reinitializing the whole Graph data structure, I only initialized the nodes that have been visited by the search. In this way the program doesn't waste time reinitializing the weights of nodes that have never been visited.
Besides implementing the first 2 ideas directly from the Assignment statement, I decided to use Sedgewick's multiway heap implementation in Program 20.10 of the book. The dijkstra function originally has a few linear time operations that must be eliminated, including resetting the pred and dist arrays as well as inserting every vertex into the priority queue. I first changed the priority queue so that it would only hold the vertices on the fringe rather than every one. Next, I used a linked list to keep track of which vertices are modified in the algorithm. With each successive call to dijkstra, instead of going through the array to reset all values, a function is called that changes the values modified by the last call to dijkstra. I added a similar function to the priority queue class, which has two arrays that need to be reset with each iteration of dijkstra.