COMP4500/7500 Advanced Algorithms & Data Structures Tutorial Exercises 5 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland August 27, 2014
1. The following is a small example of a directed acyclic graph (dag).
1 2 3 4 5 6 7 8 9
/ G is the graph, w the weight function, s the source vertex INIT-SINGLE-SOURCE(G, s)
fori = 1to|G.V|−1
for each edge (u,v) ∈ G.E RELAX(u, v, w)
for each edge (u,v) ∈ G.E if v.d > u.d + w(u, v)
return FALSE return TRUE
∗Copyright ⃝c reserved August 27, 2014
b
@R
@
ad
@ ?
@R
c
In this dag there is only one topological ordering: abcd. There are three paths from a to d: abd, abcd, and acd. A directed acyclic graph (dag) may have many distinct topological orderings. Give a dag with n nodes which has
the minimum possible number of topological orderings? Which dag has the maximum number?
2. Design an abstract algorithm to list all the topological orderings of a given directed acyclic graph. You may use the abstract traversals of graphs, and make use of abstract set and sequence operations, e.g., set union and subtraction, and sequence concatenation. You may also assume the procedure to calculate the in-degrees of a graph (from Revision 4) is available. What are the worst-case time and space complexities of your algorithm?
3. Findarecurrenceequationwhichcomputesthenumberofpathsbetweentwoverticesofadirectedacyclicgraph.
4. (CLRS Exercise 23.1-7; CLR Exercise 24.1-7)
Argue that if all edge weights of a graph are positive, then any subset of edges that connects all vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not hold if we allow some weights to be nonpositive.
5. The Bellman-Ford algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) as long as there are no negative weight cycles. The algorithm returns TRUE if and only if the graph contains no negative weight cycles that are reachable from the source. In that case the final shortest-path weight from the source s to a vertex v is stored in v.d at the termination of the algorithm. For each vertex v, on termination v.π stores the predecessor on the path from s to v. The following pseudo-code describes an implementation of the Bellman-Ford algorithm.These procedures are taken from CLRS p648–651 [3rd].
BELLMAN-FORD(G, w, s)
1
COMP4500/7500 (2014) Tutorial Exercises 5 (August 27, 2014) 2 INIT-SINGLE-SOURCE(G, s)
for each vertex v ∈ G.V v.d = ∞
1
2
3
4 s.d=0
v.π = NIL
RELAX(u, v, w)
1 ifv.d>u.d+w(u,v)
2 v.d =u.d+w(u,v)
3 v.π = u
Consider the graph on vertices v1, v2, v3, v4, v5 described by the following adjacency matrix w:
v1 v2 v3 v4 v5 v1 ∞ 5 8 −4 ∞ v2 −2 ∞ ∞ ∞ ∞ v3 ∞ −3 ∞ 9 ∞ v4 ∞ 7 ∞ ∞ 2 v5 6 ∞ 7 ∞ ∞
For vertices u and v, an entry x in row u and column v of the adjacency matrix means that the distance from u to v on the directed edge (u, v) is x, that is, w(u, v) = x. If the distance is shown as ∞ then u is not connected to v in that direction.
(a) Draw a pictorial representation of the graph, showing vertices, edges and distances.
(b) Show how the Bellman-Ford algorithm runs on this directed graph, using vertex v5 as the source. Make the following assumptions about the implementation. An adjacency list representation is used in such a way that edges are made available in lexicographic order in the loops:
“for each edge (u,v) ∈ G.E”.
This means that (vi,vj) precedes (vk,vl) if i < k or if i = k and j < l.
Give your answer by showing the values of v.d and v.π (as used in the pseudocode) for each vertex v after each iteration of the first for loop in the BELLMAN-FORD procedure.
(c) What is the return value of the BELLMAN-FORD procedure in this case (TRUE or FALSE)?
(d) Analyse the complexity of the Bellman-Ford algorithm considering the most appropriate graph represen- tation. Give your answer using O-notation in terms of |V | and |E|, where these represent the numbers of vertices and edges, respectively. Make your bound as tight as possible. Provide a justification of your analysis.
6. (CLR Exercise 25.1-4)
Let G = (V,E) be a weighted, directed graph with source vertex s, and let G be initialized by the above procedure INIT-SINGLE-SOURCE(G, s). Prove that if a sequence of relaxation steps sets s.π to a non-NIL value, then G contains a negative-weight cycle.
7. Design an algorithm to compute single-source shortest paths in a directed acyclic graph in O(|V | + |E|). (Hint: start by doing a topological sort.)
8. (CLRS Exercise 24.1-3; CLR Exercise 25.3-3)
Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the maximum over all pairs of vertices u, v ∈ V of the minimum number of edges in a shortest path from u to v. (Here, the shortest path is by weight, not the number of edges.) Suggest a simple modification to the Bellman-Ford algorithm that allows it to terminate in m + 1 passes.