算法代写｜COMP 3804/MATH 3804 Design and Analysis of Algorithms Assignment 4
Question 1:[15 points]
Covid is finally over and you want to see your best friend. You want to meet your friend as soon
as possible. Your friend lives in a different city. Both of you have cars and can start driving right
now (after determining the meeting location). You drive on a road network, i..e, you have cities
as vertices and two cities are connected via a directed edge if there is a road between them; the
weight of the directed edge (u; v) is the time it takes you to get from u to v. How would you
select the meeting location (which must be a vertex of the graph) so that you can meet as soon
as possible? Which algorithm would you use and how is this done most efficiently. The more
efficient the solution, the better the mark.
Question 2:[15 points]
Assume that you have a directed graph G =(V,E) with jV j = n nodes and jEj = m edges. Again,
this graph’s nodes are cities, the edges represent roads, the weight on an edge (u; v) is the time it
takes you to travel from node u to node v. It turns out that there are no (directed) cycles in your
particular graph. You are interested in taking the longest possible drive (you will not be able to
return to your starting point). Describe a method to compute the longest drive in this graph.
Question 3:[15 points]
Let G = (V; E) be a DAG with vertex set, V , and edge set E. Someone gives you a permutation
of the vertices and says that this is one of the possible outputs of a topological sort applied to G.
How fast can you verify that this is true? State the algorithm and the time complexity.
Question 4:[15 points]
Let G = (V; E) be a complete graph on n vertices. Apply DFS to it and describe the intervals
[pre; post] for all nodes. Are there back-edges? Are there cross-edges?
Question 5:[15 points]
You are running Dijkstra’s algorithm on a directed graph G = (V; E). While Dijkstra’s algo
rithm is executing you realize that a new edge (u; v) should be added to the graph. Vertex u has al
ready been removed from the priority queue, PQ, maintained by Dijkstra’s algorithm. Vertex v has
no other incoming edge than from u. In PQ, you still see a vertex w with cost(u; w) < cost(u; v).
I now claim that it is ok to add the (u; v) without creating errors. We only have to put it into the
PQ. Which priority value should v have in the PQ? Why would this work?