代写最短路径算法，包括BFS，DFS，Dijkstra，同时需要实现Priority Queue.
Introduction
In this assignment, you will explore a number of Shortest Path algorithms, for
both unweighted and weighted graphs. Work individually. Follow the guidelines
in the syllabus for any discussions with others. You may work in pairs on
extra credit contests, but then the extra credit will be divided among the two
of you. Extra credit entries must be bug-free to be eligible and turned in on
time (no late days).
Files
After downloading the assignment tarball from the course website, extract the
files by running:
tar -xvf lab5-handout.tgz
from a terminal window. Some of the files worth looking at are listed below.
Files you won’t necessarily modify:
Makefile
lib/.h
lib/.c
Files you should modify (and the files denoted by * will be submitted for
grading):
* heaps.c
pq_test.c
* unweighted_SP.c
bfs_test.c
dijkstra_test.c
Additionally, you should create and submit the following files:
* lib/weighted_graph.h
* weighted_graph.c
* lib/weighted_SP.h
* weighted_SP.c
* written.pdf
where written.pdf contains the answers to the written parts of the assignment.
For your convenience, we’ve provided a LATEX template (written.tex).
If you attempt the extra credit questions, you should create and submit:
* lib/stacks.h
* stacks.c
* dfs.c
dfs_test.c
Submission
To submit your programming assignment, first generate a handin archive
lab5-handin.tgz with the command
make clean && make package
then submit your lab5-handin.tgz file to your Subversion repository (svn) for
the class. Once you’ve completed all problems, you should also submit your
written.pdf to Gradescope.
Note that your code will not be graded until after the due date. It is your
responsibility to test your code on the CSIL machines and proofread your
writeup thoroughly before submitting. Code that does not compile will not
receive any points.
Priority Queues
In this assignment, we will learn to solve Shortest Paths Problems using BFS
and Dijkstra’s algorithm, both of which require the Priority Queues abstract
data type. During lecture, we looked at priority queues as the generalization
of stacks and queues, where we insert and delete elements in the order of
their assigned priority, represented by an integer. The element with the
highest priority, which translate to minimal integer priority value, will
always be removed first. For the purpose of this lab, we will be dealing with
priority queues with bounded capacity.
Bounding the size of priority queues is not uncommon in real life. For
example, in an operating system, the runnable processes might be stored in a
priority queue, so as to be executed in the order of their assigned
priorities. Similarly, in a network router packets may be routed according to
some assigned priorities. In both cases, bounding the size of the queues helps
to prevent so-called denialof-service attacks where a system is essentially
disabled by flooding its task store. This can happen accidentally or on
purpose by a malicious attacker.
As discussed in lecture, we choose to implement priority queues using heaps.
Recall the two crucial invariants of heaps:
- Ordering invariant: The key of each node in the tree is less than or equal to all of its children’s keys. So the minimal element is always at the root.
- Shape invariant: We fill the tree level by level, from left to right, which means that the shape of the tree is completely determined by the number of elements in it.
Task
In heaps.c, implement the following functions, as required by the priority
queue data type:
heap pq_new(unsigned int capacity, priority_fun elem_priority);
bool pq_empty(heap H);
bool pq_full(heap H);
void pq_insert(heap H, elem e);
elem pq_min(heap H);
elem pq_delmin(heap H);
void pq_free(heap H, void (*elem_free)());
each of which evaluates to the following:
pq_new: Allocates the memory needed for an empty priority queue with given capacity and priority function that takes an element and returns its assigned priority
pq_empty: Determines if heap H is empty
pq_full: Determines if heap H is full
pq_insert: Inserts the element e into the heap, and restores heap invariant
pq_min: Returns the element with minimum priority in H
pq_delmin: Removes the element with minimum priority from H and returns it
pq_free: Frees memory used by the heap, as well as that of each element if there’s any
Although not mandatory, we recommend you represent heaps as arrays. A first
thought on how to represent a heap would be using structs with pointers for
each node. However, there is a more elegant representation using arrays. We
use binary numbers as addresses of tree nodes. Assume a node has index i. Then
we append a 0 to the binary representation of i to obtain the index for the
left child and a 1 to obtain the index of the right child. We start at the
root with the number 1. Mapping this back to numeric operations, for a node at
index i we obtain its left child as 2 i, its right child as 2 i + 1, and its
parent as i/2. Care must be taken, since any of these may be out of bounds of
the array.
We have provided a few simple tests in pq_test.c. Please add more of your own
tests to it, and test your implementation of priority queues by running on
command line:
$ make priorityqueue
$ ./priorityqueue
Unweighted Shortest Paths
Unweighted graphs
Suppose you are interested in finding how close two vertices are in a given
unweighted graph. In particular, given two vertices u and v, you want to find
out the length of the shortest path from u to v. The graphs in this section
are directed, simple, and unweighted.
If you dig around the handout library, you will find a complete C
implementation of unweighted graph data structure in lib/unweighted_graph.h
and lib/unweighted_graph.c. You may use, or modify them as you want.
Specifically, we use the adjacency list representation, where we keep a linked
list of neighbors for each vertex. So the entire graph is represented by a
length-n array of linked lists, where n is the number of vertices in the
graph. You might want to check out the following operations:
- ugraph ugraph_new(unsigned int numvert) creates a new unweighted graph with numvert vertices.
- void ugraph_free(ugraph G) frees the memory used by graph.
- unsigned int ugraph_size(ugraph G) returns the number of vertices in the graph.
- bool ugraph_hasedge(ugraph G, vertex v, vertex w) determines if (v,w) is an edge in graph G
- void ugraph_addedge(ugraph G, vertex v, vertex w) connects the edge (v,w), with the precondition that the edge did not exist in G before.
- adjlist *ugraph_neighbors(ugraph G, vertex v) returns a linked list of the neighbors of vertex v. This adjacency list is owned by the graph and should not be modified by the user.
BFS
Now we are ready to find the shortest path between any two vertices in the
graph. For unweighted graph, the first algorithm we consider is breadth-first
search where we explore the graph layer by layer.
Task
In unweighted_SP.c, implement the function:
int bfs_iter(graph G, vertex start, vertex target, vertex *sp);
—|—
which searches for the shortest path from start to target in the graph G using
BFS, and return the path length and store the path in sp if found, otherwise
return -1. Note that sp is inclusive, meaning that it should also include both
start and target. So the length of array sp is 1 plus the path length. Some
special cases:
- When start == target, bfs_iter should evaluate to 0, and sp = {start}
- If (start, target) is an edge, bfs_iter should evaluate to 1, and sp = {start, target}
One additional requirement for this task is that, during the graph search, you
should print out the vertex you are visiting at every step. More precisely,
the command line should look like:
$ make bfs
$ ./bfs
Visiting 3
Visiting 5
…
Visiting 10
Don’t forget to add your own tests to bfs_test.c for more comprehensive
testing.
Weighted Shortest Paths
While you are testing your shortest path algorithm from last section on
different graphs, you realize that the BFS does not always give you the
correct result on weighted graphs. So you decided to implement Dijkstra’s
algorithm to handle graphs with weighted edges.
This section is identical to the previous except that the input graph is now
directed, simple, and weighted. You may assume that all weights are strictly
positive (no edge will have an edge weight of 0).
Weighted graphs and Dijkstra’s Algorithm
Task
You may have discovered already, but the files for the weighted graph data
structure do not exist yet. So for this part of the assignment, you will need
to create the following files:
- lib/weighted_graph.h: Interface for weight graph data structure
- weighted_graph.c: Implementation of the weight graph data structure
- lib/weighted_SP.h: Interface for Dijkstra’s algorithm
- weighted_SP.c: Implementation of Dijkstra’s algorithm
Their structure should assemble that of the corresponding unweighted version.
So feel free to copypaste, but make sure you do not have any correctness
mistakes! (Otherwise, you’ll be penalized in both sections for the same
error…)
Note that all requirements from previous section still apply here, including
the command line print statements that should display the graph search order.
So after you add your own tests to dijkstra_test.c, you may run you program:
$ make dijkstra
$ ./dijkstra
Visiting 3
Visiting 5
…
Visiting 10
Cycle Detection (Extra Credits)
Note: This part of the lab is for extra credit. Make sure you complete the
other tasks before attempting this section.
The graphs in this section are directed, simple, and unweighted. And we will
implement DFS algorithm to determine if a graph contains a directed cycle.
Iterative DFS
Recall from lecture, we implement the iterative DFS algorithm using stacks,
which are a LIFO (last in, first out) data structure. This is just like
ordinary references to stack, e.g. a stack of books. Here is the interface for
stacks, as discussed in lecture:
stack stack_new();
bool stack_empty(stack S);
void push(stack S, elem x);
elem pop(stack S)
—|—
In fact, we can use priority queues to implement stacks. We do this by
choosing appropriate priority values for the elements we insert into the
priority queue such that they’ll be removed in the order we want them to be to
satisfy the LIFO property of a stack.
Specifically, to get a priority queue to behave like a LIFO stack, we insert
elements in decreasing priority order, so that the thing most recently
inserted into the priority queue has lowest priority and will be removed in a
delmin operation.
Task 1
Create the files lib/stacks.h and stacks.c that implement the LIFO stack
interface using priority queues.
Task 2
Create a file dfs.c that contains the function:
bool has_cycle(graph G);
—|—
that determines if there are any cycles in the graph by iterative DFS. Since
we are dealing with simple graphs, there is no self-loops (cycle of length 1).
However, there could be cycles of length 2. Hint: A directed graph has a cycle
if and only if a DFS over the vertices has a back edge. (We call an edge (u,
v) a tree edge if during DFS we traversed down to v from u. And a non-tree
edge (u, v) is a back edge if v is an ancestor of u in the DFS tree.)
To test your implementation, create a file dfs_test.c similar to bfs_test.c,
and run:
$ make dfs_cycle
$ ./dfs_cycle
True/False
For the following True/False questions, clearly state your choice and explain
in a few sentences about your reasons.
Task 1
TRUE or FALSE: Kruskal’s algorithm for minimum spanning tree works with
negative edge weights.
Task 2
TRUE or FALSE: One can find a maximum weight spanning tree of a connected
graph by negating all of the edge weights and using a minimum spanning tree
algorithm.
Task 3
TRUE or FALSE: The heaviest edge in a undirected weighted connected graph
cannot belong to minimum spanning tree.
DFS
A DFS order is a sequence of vertices of a graph in the order in which they
are first visited by depth-first search (DFS).
One DFS order of this graph is {A, B, C, X, H, M}.
Task
List ALL other possible DFS orders for this graph, given source vertex A.
