算法分析代写|COMP 3804/MATH 3804 Assignment 3

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

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
modified 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 jV j = 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 modified, 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!