Question 1 [20 marks]

Show how Bellman-Ford’s and Dijkstra’s algorithms would compute the shortest paths from A to all vertices of the graph shown in Figure 2.  Illustrate the algorithms as shown in class:  Bellman- Ford via a sequence of graphs (see slide 22). Dijkstra’s (see slide 36) by filling in a table with step numbers as row index, vertices as column index, and d[],  [] values as entries.  Circle a d[]-value when it is finalized, i.e., when it become [] .

Figure 1: The input graph for Question 1.

Question 2 [20 marks]

Assume that we are given an undirected graph G=(V,E). Consider that Dijkstra’s algorithm found a shortest path in G, called SP, between two nodes A and X of V. Is it true or false that if we reverse the nodes on SP, we get a shortest path from X to A? Prove or disprove.

Question 3 [10 marks]

1. List three different topological orderings for the enclosed graph.

2.  Draw a (connected, directed) graph for which no topological sorting order exists.

Figure 2: The input graph for Question 3.

Question 4 [10 marks]

Can Dijkstra’s algorithm be used to determine if a graph is connected?  How does that compare to algorithms for graph connectivity that you may know from previous classes or that you read up (and cite)? Just list the algorithm used and compare the time complexity.

Question 5 [10 marks]

We said that the input to PRIMs algorithm is a connected, undirected graph. Suppose by accident, we give an input graph that is not connected. What would happen?

Question 6 [12 marks]

Suppose that we are considering a directed, acyclic graph G. A Hamiltonian path is a path in G that visits each vertex of G exactly once.  Considering the below four statements, when does topological sorting of G yield a unique solution? Draw a counter-example and argue for each of the four statements in case it is incorrect below is incorrect and prove its correctness, otherwise.