CSCI 3104: Algorithms
1. Answer the following questions for the graph shown below:
(a) Draw the DFS search tree with starting vertex E and break ties alphabetically.
(b) Assuming unit edge length (i.e., ignore edge weight), draw the BFS search tree
with starting vertex E and break ties alphabetically.
(c) Suppose the Dijkstras algorithm is run on the graph with starting vertex E:
(i) draw a table showing the intermediate distance values of all vertices at each
iteration of the algorithm; (ii) show the final shortest-path tree.
2. Often there are multiple shortest paths between two nodes of a graph. Give a lineartime algorithm for the following task.
Input : Undirected graph G = (V, E) with unit edge lengths; nodes u, v ∈ V .
Output : The number of distinct shortest paths from u to v.
3. You are given a strongly connected directed graph G = (V, E) with positive edge
weights along with a particular node v0 ∈ V . Give an efficient algorithm for finding
shortest paths between all pairs of nodes, with the one restriction that these paths
must all pass through v0. Describe your algorithm in words or write down the pseudo
code. And analyze its time complexity.
