CE2001/CZ2001 ALGORITHMS
Project 2: Graph Algorithms

1. Problem
You are given an undirected unweighted graph G, which represents a city’s road
network with n nodes being intersections/endpoints and m edges being roads. Among
the n nodes, h of them are hospitals and you are interested in finding, for each node,
the distance (i.e., the number of edges in the shortest path) from each node to the
nearest hospital. h could take any value from 1 to n.
(a) Design an algorithm for computing the distance from each node in G to its
nearest hospital. Output the distance and the shortest path for each node to a
file.
(b) Design an algorithm to complete the task (a) but its time complexity should not
depend on the total number of hospitals h. You could skip (b) if your algorithm
in (a) already satisfies this complexity constraint.
(c) In some circumstances (e.g., big disasters, fires, etc.), having the distance from
each node to the nearest hospital is not good enough. Instead, we are
interested in finding the distances to top-2 nearest hospitals from each node.
Revise your algorithm in (b) to accommodate this new requirement. If revision
is not possible, you are free to design a new algorithm.
(d) Propose an algorithm that works generally for computing the distances from
each node to top-k nearest hospitals for an input value of k.

2. Data Source
As a quick start and for demonstration purpose, you could use a small input graph
obtained from a random graph generator (http://graphstream-
project.org/doc/Generators/Random-graph-generator/).
Your designed algorithms are required to be tested on at least one of the large-scale
real road networks downloaded from https://snap.stanford.edu/data/index.html#road.
For both random graphs and real road networks, you should generate the number and
the locations of hospitals to be used as input.



3. Implementation
You are required to implement all algorithms designed in this project.
[Input] The input for tasks (a)-(c) is a graph with hospitals marked, and that for task
(d) has an additional input of k. Your program should take two input files for the graph:
file1 stores the graph structure in the same format as the real road network file
downloaded; and file2 stores the hospital information. The format of file2 is as follows:
the first line is “# num”, giving the total number of hospitals; then each hospital is
placed in a single line by showing its node ID only. A sample is given below:
# 4
3
10
19
34
[Output] Outputs of the program should be fed to a file, unless for demonstration
purpose.
[Experiments] Your program should be tested on at least one random graph and one
real road network. Note that the real road network is of large-scale (over 1 million
nodes/edges) and your program should be able to handle this input scale
(memory/space issues may arise). You are required to conduct empirical study to see
the effects of h and k on the performance of various algorithms and conclude if the
empirical findings are consistent with your theoretic analysis.
[Others] The interface should be user-friendly so that lab supervisor can test on
arbitrary input graphs. The work has to be well documented and submitted to their lab
supervisors for verification.

4. Design and Analysis of Algorithm
You are required to describe your algorithms clearly, prove their correctness, and
analyze their asymptotic time complexity. The lab supervisor will evaluate your work
based on the correctness and completeness of analysis of algorithm and originality of
the proposed algorithms. All reference materials have to stated clearly in the report.
Students is reminded that plagiarism is a very serious academic offence. If any student
may not knowingly intend to plagiarise, but that should not be used as an excuse for
plagiarism. Students should seek clarification from lecturers or lab supervisors if they
are unsure whether or not they are plagiarising the work of another person.

欢迎咨询51作业君