DSHW4

Data Structure HW4 Goal: Study the Properties of "Small World" and Compare Different Data Structures

1. Generate a cycle of 1000 nodes. Each edge has length 1.
2. Add x random edges. Each random edge has the same length y.
3. Sample z pairs of source and destination and compute the average shortest distance (d) of these z source-destination pairs. You need to use 2 different structures to store graphs. You need to use 2 different structures of heaps. (In the report, give the name of the data structures that you use, e.g., array and Binomial heap).

Thus, you have 4 different implementations of Dijkstra's Algorithm Draw a graph where x = 100. Give references to the source code/libraries that you use. In your report, you have to give references to the source code or libraries that you use.

Answer the following questions. You need to support your answers with experimental results. You also need to explain how you obtain the results.

1. What is the relationship between x and d?
2. What is the relationship between y and d?
3. How to choose z properly to reflect the true average distance between all pairs of source and destination?
4. Which implementation of Dijkstra's Algorithm is the fastest?