# 算法分析 | COMP 3804/MATH 3804 Design and Analysis of Algorithms I Assignment 3

Question 1:[5 points]

Dijkstra’s algorithm is not applicable for negatively weighted edges. So, why don’t we just ”scale everything up” by adding to each edge-weight: one plus the absolute value of the globally smallest (negative) weight. This way, all weights are positive. Does the algorithm, when applied to the modiﬁed graph, correctly compute the shortest path in the orginal graph? If so, give a proof; if not, give a counter-example.

Question 2:[20 points]

Let us assume that we have a directed graph G =(V,E) with |V | = n nodes of which there are k starting nodes from which we would like to know their shortest path distances to a common destination node (many-to-one problem).

• We could solve the problem by applying Dijkstra’s algorithm k times, ones for each of the k starting nodes. What is the time complexity (stated in terms of n and k)?

• Alternately, we could start at the destination node and somehow go backwards. Describe how this would work, i.e., how would we modify Dijkstra’s algorithm and/or its input to achieve this? Then, state the time complexity of this solution to our original problem. (Do not forget to argue why the algorithm, as modiﬁed, is correct!)

Question 3:[15 points]

Suppose we want to compute the shortest path tree from node, A, using Bellman-Ford for the graph shown below in Figure 1. Show how Bellman-Ford would work on this graphs as input.

Question 4:[15 points]

Let n be the number of vertices of a given triangulation of a convex polygon.

• How many triangles does the triangulation consist of? Prove your statement by induction on n.

• Consider now the simplest algorithm for computing weighted shortest paths, as described in class which places the same number of Steinerpoints on each edge of the triangulation. Assume that we place, say 7 Steinerpoints, on each edge of the triangulation. Precisely, how many edges does the algorithm add? Argue!

Question 5:[15 points]

Consider the graph given in Figure 3 above.

• Run DFS on the graph and classify each edge as being either: Tree edge, Forward edge, Back edge, or Cross edge. Show and argue: the algorithm execution, pre(v) and post(v) time intervals and the edge-classiﬁcation. (An edge type may or may not appear in a particular graph.)

• Find a topological order of the nodes or argue that no such order can exist.

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