本次加拿大代写是一个算法设计与分析的assignment

**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?

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。