主观题：Shortest Path Algorithm with Heaps
Shortest path problems are ones of the most fundamental combinatorial optimization problems with many applications, both direct and as subroutines in other combinatorial optimization algorithms. Algorithms for these problems have been studied since 1950's and still remain an active area of research.
In this project you are supposed to compute the shortest paths using Dijkstra's algorithm. The implementation shall be based on a min-priority queue, such as a Fibonacci heap. The goal of the project is to find the best data structure for the Dijkstra's algorithm.
Your tasks are:
- (1) Implement the algorithm with at least two different heap structures, while Fibonacci heap must be one of them.
- (2) Use the USA road networks for evaluation. The data sets can be downloaded from http://www.dis.uniroma1.it/challenge9/download.shtml which provides the benchmarks for the **9th DIMACS Implementation Challenge**. (**Note:** you must **only list the download links** of these test data sets instead of uploading them with your reports.)
- (3) At least 1000 pairs of query are required in evaluating the run times of the algorithm with various of implementations.
### Grading Policy:
**Programming:** Implement Dijkstra's algorithm with Fibonacci heap and other heaps (6 pts.). Write a test of performance program (3 pts.). **All the codes must be sufficiently commented.**
**Testing:** Provide the necessary inputs for testing and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (3 pts.).
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to contain the descriptions of at least 2 heap structures (+1.4 pt.), together with all the key operations (+0.6 pt.). Deduct points if:
- the algorithm specification is not complete -- Fibonacci heap is not discussed; (-0.7)
- the algorithm specification is not complete – only one heap structure is discussed; (-0.7)
- the algorithm specification is not complete -- they are supposed to specify all the key operations of the chosen data structures; (-0.1 ~ 0.6)
- not making their algorithm easier to understand than a simple program (-0.5)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 4 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+1 pts.) and the performance (+3 pts.). Deduct points if:
- the testing results are not complete – the correctness testing is missing(-1)
- the testing is run on a much simpler data set than the required benchmark set; (-1~3)
- others – please specify in the final comments.
Item 5: 3 points
In Chapter 4, analysis of both the time (+1 pt.) and space (+1 pt.) complexities must be given, together with sufficient discussions on the testing results (+1 pt.). Deduct points if:
- the plot is missing; (-1)
- there is no comments on analyzing why one implementation is faster than another; (-1)
- **analysis** of the **complexities** of time and/or space is missing -- they must show how they have reached their conclusions, instead of simply listing them (-1)
- others – please specify in the final comments.
Item 6: 9 points
The programmer is supposed to implement Dijkstra's algorithm with Fibonacci heap and other heaps (+6 pts.), together with a test of performance program (+3 pts.). Deduct points if:
- not all the necessary operations are implemented (-1 ~ 6)
- the testing program is missing (-3)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-9)
- others – please specify in the final comments.
In this project you are supposed to compute the shortest paths using Dijkstra's algorithm. The implementation shall be based on a min-priority queue, such as a Fibonacci heap. The goal of the project is to find the best data structure for the Dijkstra's algorithm.
Your tasks are:
- (1) Implement the algorithm with at least two different heap structures, while Fibonacci heap must be one of them.
- (2) Use the USA road networks for evaluation. The data sets can be downloaded from http://www.dis.uniroma1.it/challenge9/download.shtml which provides the benchmarks for the **9th DIMACS Implementation Challenge**. (**Note:** you must **only list the download links** of these test data sets instead of uploading them with your reports.)
- (3) At least 1000 pairs of query are required in evaluating the run times of the algorithm with various of implementations.
### Grading Policy:
**Programming:** Implement Dijkstra's algorithm with Fibonacci heap and other heaps (6 pts.). Write a test of performance program (3 pts.). **All the codes must be sufficiently commented.**
**Testing:** Provide the necessary inputs for testing and give the run time table (2 pts.). Plot the run times vs. input sizes for illustration (2 pts.). Write analysis and comments (3 pts.).
**Documentation:** Chapter 1 (1 pt.), Chapter 2 (2 pts.), and finally a complete report (1 point for overall style of documentation).
答案：Rubric items: 6
Item 1: 1 point
The cover page must be presented with the title and the date of completion (+ 0.2 pts.). A complete problem description must be given in Chapter 1 (+0.8 pts.). Deduct points if:
- the cover page is not complete (-0.2)
- the introduction is a simple copy + paste of the assignment statement (-0.3)
- the introduction is not very clear -- in this chapter they are supposed to make it clear WHAT is to be done, besides why they are doing it (-0.1 ~ 0.5)
- others – please specify in the final comments.
Item 2: 2 points
Chapter 2 is supposed to contain the descriptions of at least 2 heap structures (+1.4 pt.), together with all the key operations (+0.6 pt.). Deduct points if:
- the algorithm specification is not complete -- Fibonacci heap is not discussed; (-0.7)
- the algorithm specification is not complete – only one heap structure is discussed; (-0.7)
- the algorithm specification is not complete -- they are supposed to specify all the key operations of the chosen data structures; (-0.1 ~ 0.6)
- not making their algorithm easier to understand than a simple program (-0.5)
- only a program + comments, which is not acceptable (-1)
- others – please specify in the final comments.
Item 3: 1 point
The overall style of documentation is supposed to be neat and clear. Deduct (at most 1) point if:
- the document looks like a patch work (-1)
- messy – some of the data in the charts and tables are missing (-1)
- the hand-in is not zipped with proper folders (-1)
- the hand-in is not complete – some files are missing (-1)
- others – please specify in the final comments.
Item 4: 4 points
A complete table of testing data must be given in Chapter 3, including testing the correctness (+1 pts.) and the performance (+3 pts.). Deduct points if:
- the testing results are not complete – the correctness testing is missing(-1)
- the testing is run on a much simpler data set than the required benchmark set; (-1~3)
- others – please specify in the final comments.
Item 5: 3 points
In Chapter 4, analysis of both the time (+1 pt.) and space (+1 pt.) complexities must be given, together with sufficient discussions on the testing results (+1 pt.). Deduct points if:
- the plot is missing; (-1)
- there is no comments on analyzing why one implementation is faster than another; (-1)
- **analysis** of the **complexities** of time and/or space is missing -- they must show how they have reached their conclusions, instead of simply listing them (-1)
- others – please specify in the final comments.
Item 6: 9 points
The programmer is supposed to implement Dijkstra's algorithm with Fibonacci heap and other heaps (+6 pts.), together with a test of performance program (+3 pts.). Deduct points if:
- not all the necessary operations are implemented (-1 ~ 6)
- the testing program is missing (-3)
- some of the programs are not working properly (-1 ~ 3)
- the programs are not well-commented (-9)
- others – please specify in the final comments.
