Project 2-Shortest Path Algorithm with Heaps

Project 2 - Shortest Path Algorithm with Heaps

我的teamwork部分，是比较难的一节.

Project Description

In this project, you are supposed to implement the Dijkstra’s algorithm using different heaps, and compare the performance of these implementations. Only three heap operations Insertion, Delete-Min and Decrease-Key are considered in this project.

1. Fibonacci Heaps

   A Fibonacci heap is a priority queue consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures. You may refer to Chapter 19 of Introduction to Algorithms (third edition) for details. You should do the followings.

   • Give simple theoretical analysis for Fibonacci heaps. More specifically, you have the following tasks.
     • An introduction of the Fibonacci heap, including how the keys are organized and how the operations are supported, including but not limited to Insertion, Delete-Min and Decrease-Key.
     • Brief analysis on the worst-case cot of Insertion, Delete-Min and Decrease-Key, and a list of the amortized cost of these three operations. (The amortized analysis, which is elaborated in Chapter 19 of Introduction to Algorithms, is not required.)
   • Choose another priority queue (heap) structure from the binary heap, the leftist heap, the skew heap and the binomial queue, and give a theoretical comparison between this and the Fibonacci heap.
   • Implement the Fibonacci heap and the other heap structure. Test the correctness of your implementations on simple cases. You do not have to compare their performances on large-scale inputs in this step.

2. Heap-Optimized Dijkstra's Algorithm

   The Dijkstra's algorithm solves the shortest path problem on graphs with non-negative edge weights. By heap optimization, the efficiency of relaxation in the Dijkstra's algorithm is improved.

   Now you are supposed to implement the heap-optimized Dijkstra's algorithm. The implementation shall be based on a min-priority queue, such as a Fibonacci heap. The goal of this step is to find the best data structure for the Dijkstra's algorithm.

   In this step, you have the following tasks.

   • Implement the Dijkstra's algorithm using the Fibonacci heap and the other heap structure you chose earlier. Test the correctness of your implementations on simple graphs created by your own.
   • Give a theoretical analysis of the running time of these two different implementations.
   • Do experiment to compare the performance of these two implementations on graph with different density. You may generate graphs with \(m=\Theta(n)\), \(m=\Theta(n^{1.5})\), and \(m=\Theta(n^2)\)，and test how the running time of these two implementations increase against n.
   • Evaluate the implementations using the USA road networks. The data sets can be downloaded from this page. You should evaluate your implementations on road networks of different sizes. For each network, at least 1000 queries are required in evaluating the run times of the implementations. Each query is a pair of a source and a sink, and the algorithm should return the length of the shortest between them.

Group Presentation Submission

You should upload zip to 2-1 and slides to 2-2.

You are required to upload your submission materials in a zip file that contains the project report (in pdf format), the source code (including the implementation and the testing code), and the testing data. The file structure should be organized as follows:

PxGyy.zip
├── code
│   ├── source code files (*.c, *.h, ...)
│   └── readme.txt (Instructions on how to build the executable file and how to run it)
├── documents
│   ├── PxGyy.pdf
│   └── Other materials if necessary
└── testcases
    ├── 1.in (Input file 1, plain text in UTF-8, the same below)
    ├── 1.out (Output file 1)
    ├── 2.in
    ├── 2.out
    ├── ...
    └── readme.txt (Simple specification of testing data)

In the name of report document and zip PxGyy.pdf/zip, x is the project number (2 for this project) and yy is your group number with 2 digits, 01 for example. E.g. P2G01.zip.

• report

  The report should be written clearly and neatly in English. It should starts with a title page containing the title, the group id if you work as a group, the author names, and an abstract summarizing your work. Within the main text following the title page, the report should present the following contents.

  • A clear description of this project.
  • An introduction of the Fibonacci heap.
  • A theoretical analysis of the worst-case cost of Fibonacci heap. Only Insertion, Delete-Min, and Decrease-Key are considered.
  • A theoretical comparison between the Fibonacci heap and the other heap. A table of running times of all the operations is sufficient. There is no need to give the details of the analysis.
  • A theoretical analysis of the running time of the Dijkstra's algorithm with the two different implementations.
  • A description of your experiment and its result. (All we care here is the running time evaluation. As to the correctness test, you only need to submit the test code.) You should state which networks are used, how the graphs are stored, how many queries you have done, how the resulting data is obtained, as well as other things that you think are important. As to the result, you should give a table showing the running time of each implementation on each graph. You should also plot the running times vs. graph sizes for illustration. You should also analyze the experiment result.
  • Conclusion and discussion.

  You are encouraged to write your report using \(\LaTeX\) (try overleaf.com), but Microsoft Word is also fine.

• code

  Generally, you are required to implement in C or C++. You should not use any STL if you implement in C++. You may ask TA for permission if you want to use a language other than C or C++. The source code should be in good style, and have sufficient comments.

• test

  All the testing data should be stored and uploaded (even if they are randomly generated).

  A readme.txt that simply specifies the testing data is required.

• slides

  The slides should be named as PxGyy.pptx, where x is the project id and yy is your group number with 2 digits, 01 for example. E.g. P2G01.pptx. The slides should submitted to 2-2.

  Pay attention that only the group leader needs to upload the materials and submit them. Other group members do not need to upload anything, but should click the "submit" button of 2-1 and 2-2 to be graded.

Individual Bonus Submit

You should submit a zip to 2-3, and the requirement of zip is the same as above. The zip file should be named as Px_id_name.zip instead, where id is your student id and name is in English without spaces. E.g. P2_3240100000_ZhangSan.zip.

Final Report

Overleaf项目地址