C代写:CS162 Short

代写最短路径算法,包括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:

1
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:

1
2
3
4
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:

1
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.