Written Assignment
In All graph algorithms, vertices should be processed alphabetically whenever there is choice among equivalent vertices.
Updated 2017-11-08: Problem 7(a) should use the graph from problem 4 (not problem 2).
BFS and DFS
Problem 1) (30 points) For the following graph:
(9 points) Perform BFS on the following graph starting at vertex A show v.d and v.π for each vertex v.
(3 points) Draw the Breadth first predecessor tree resulting from running the algorithm in part (a).
(9 points) Perform DFS on the graph and process the vertices alphabetically. Show start and finish times as well as v.π
(3 points) Draw the DFS predecessor tree resulting from running the algorithm in part (c)
(3 points) Write the parenthesis string resulting from running DFS
(3 points) Classify the edges (tree, back, forward, cross).
Problem 2) (5 points) Run the strongly connected component detection algorithm discussed in class on the following graph. Show the start and finish time during execution of depth first search, the parenthesis string and then process the string to get the strongly connected components.
Minimum Spanning Trees
Problem 3) (15 points) Consider the following graph:
(7 points) Run Kruskal’s algorithm on the graph above. Show the edges chosen at each step (no need to show the set union data structure)
(8 points) Run Prim’s algorithm on the graph above. Show the edges chosen at each step as well as and changes at each step
Bellman-Ford and Dijkstra’s Algorithms
C
GProblem 4) (10 points) Run Bellman-Ford algorithm on the following graph. Process edges alphabetically AB first then AC second AD third and FG last. Show the relaxation of edges at each step. You can stop once relaxation doesn’t result in change.
Problem 5) (10 points) Run Dijkstra’s algorithm on the following graph starting from vertex A. Show the relaxation of edges and the open list at each step.
Problem 6) (10 points) Dijkstra’s algorithm described in the book only works for edges with positive weights (even without negative cycles the algorithm could still fail). Show an example by drawing a graph with negative weights but NO negative cycles such that Dijkstra’s algorithm computes the incorrect shortest path for one or more of the vertices.
Problem 7) (20 points) Motivation: When using navigation system app, we often would like to get the shortest 3 paths from source to destination instead of just the shortest path. This is especially useful when driver would like to avoid highways or toll roads or even prefers a more scenic route.
Problem: Given a weighted undirected graph with no negative weights, find the shortest 3 paths from source s to destination vertex t.
One algorithm to solve this problem is a modification of Dijkstra’s algorithm where we keep a queue of paths from source to every vertex and for each vertex we maintain property , the number of paths from to vertex . At every iteration, we remove from the with the shortest distance and then add into all paths where is a neighbor of u and update for each of these neighbors.
Whenever a path removed from QPaths reaches the destination (i.e is a Pt), we add the path to a list of results. Once number of solutions found reaches 3, we quit.
THREE_SHORTEST_PATHS(G, s, t) // s is the source and t is the destination vertices.
INITIALIZE_VERTICES(G)
solutions = //Set of solution paths from s to t
Ps = {s} // A path from s to s
Ps.cost = 0 //Cost of this path is zero
Insert Ps into QPaths
while QPaths != and |solutions| < 3
Pu = EXTRACT_MIN(QPaths) //Extract path with smallest cost
u.c = u.c + 1 //We found a path from s to u
if u == t //Check if it’s the destination
solutions = solutions Pu
continue
if u.c ≤ 3
for each vertex v G.Adj[u] and v ∉Pu //to ensure no cycles
Pv = Pu v
Pv.cost = Pu.cost + w(u, v)
Insert Pv into QPaths
return solutions
INITIALIZE_VERTICES(G)
for each v in V
v.c = 0
(8 points) Run the algorithm described above on the graph in problem 4 from source to destination
(4 points) In the algorithm we never store more than three paths to node on the route to (line 12 ensures it). This step is not necessary and the algorithm will compute the correct answer regardless of that step. That said, prove that we never need to store more than three paths to any node on the path to . (You can prove this informally)
(4 points) What’s the running time of the algorithm described above if Extract_Min can be done in O(log n)? Briefly justify your answer
(4 points) Informally prove that the algorithm will never store a path in QPaths more than once. In other words, once a path is removed from QPaths, it will never be added into QPaths again.