Consider a directed acyclic graph with V vertices and E edges.

(i) What is meant by a total order on the vertices consistent with the edges? [2 marks]

(ii) Describe an O(E + V ) algorithm to compute such a total order. [3 marks]

(b) Consider a directed graph with non-negative edge costs and with a given start vertex s.

(i) Dijkstra’s algorithm computes distances from s to every other vertex. Give psuedocode for Dijkstra’s algorithm. [4 marks]

(ii) Dijkstra’s algorithm can be implemented using a Fibonacci heap. State the complexity of using this implementation. Justify your answer carefully. [Note: Your answer should include mention of amortized costs.] [4 marks]

(c) Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s.

(i) Devise an algorithm to compute distances from s in O(E +V ) time. Justify why your algorithm is correct. [4 marks]

(ii) Explain, with an example, why Dijkstra’s algorithm might take ?(V log V ) time. [3 marks]

Answer rating: 100% (QA)

The detailed answer for the above question is provided below a i A total order on the vertices of a directed acyclic graph DAG is a linear ordering of the vertices such that for every edge u v in the ... View the full answer