Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 5/5.
To connect the vertices in the graph to the heap, maintain an int array called map. This array contains a slot for each vertex in the graph. If a vertex with index i is in the heap, then map[i] contains the slot in the heap that i is in. If a vertex with index i is not in the heap, then map[i] contains -1. Recall that at any time during the running of the DSP algorithm, the vertices in V - S need to be stored in the heap. As the heap changes, map will also have to be updated. However, the updates to map only add a constant overhead to the running time of the heap operations.
Here are some specifics. Start with Lafore's heap class and modify it into a min-heap. Then add an integer array called map as a data member to this class. Each element that is inserted into the heap comes with two descriptors: a key and a priority. In the case of our application (the DSP algorithm) we insert vertices into the heap and these are decribed by an index (the key) and a d-value (the priority). Also, the DSP algorithm repeatedly calls the change function in the heap class. The change function in the heap class currently takes an index that points to a slot in heapArray. However, for the DSP algorithm, we need a change function that takes as index that points to a slot in map.
After implementing the DSP algorithm, run it on the graph shown in Problem 1 and make sure that it computes a correct shortest path tree.