Algorithm
Algorithm | assignment – 这个题目属于一个Algorithm的代写任务, 涵盖了Algorithm等方面, 该题目是值得借鉴的assignment代写的题目
COMP3121/9101 22T2 assignment 4, Question 3 (Algo Rhythm, z1234567)
Question 3
You are given a simple directed weighted graph withnvertices andmedges. The edge weights maybe negative, but there are no cycles whose sum of edge weights is negative.
3.1 [10 marks]An edgeeis said to beusefulif there is some pair of verticesuandvsuch that ebelongs toat least oneshortest path fromutov.
Design an Algorithm which runs inO(n^3 ) and determines the set of useful edges.
Labeling the vertices ofVasv 1 , v 2 ,... , vn, an edgee= (vi, vj) from vertexvito vertexvjis
not useful if there is a pathpfromvitovjsuch that the sum of the edge weights ofpis less
than the edge weight ofe. because ifeis useful, then there is some pair of verticesuandv
such thatebelongs to one shortest pathqfromutov, if we replace the edgeewith the path
pinq, then we will get a shorter path fromutov, which is contradiction withqis shortest.
If there is no pathpfromvitovjsuch that the sum of the edge weights of the pathpis less
than the edge weight ofe, thene= (vi, vj) will be the shortest path fromvitovj, that ise
belongs to one shortest path fromvitovj, theneis useful.
Thus an edgee= (vi, vj) is useful if and only if the edgeeitself is one shortest path fromvi
tovj.
We use the Floyd-Warshall algorithm to compute the shortest path lengthopt(i, j, k) of any
pair of verticesvi, vj, and a edge (vi, vj) is useful if and only ifopt(i, j,0) =opt(i, j, n). Since
the complexity of Floyd-Warshall algorithm isO(n^3 ), and for each edge it takesO(1) to
check if the edge is useful. Since the number of edges isO(n^2 ), thus the algorithm also run
inO(n^3 +n^2 ) =O(n^3 ) time.
3.2 [10 marks]An edge is said to bevery usefulif there is some pair of verticesuandvsuch thatebelongs toeveryshortest path fromutov.
Design an algorithm which runs inO(n^3 ) and determines the set of very useful edges.
If edgee= (vi, vj) is very useful, then the edge itself is a shortest path fromvitovj, this
should be the only shortest path fromvitovj, because if there is another shortest pathp
fromvitovj, theneshould not belongs top, otherwise, whenw(e)<0, then there will be a
negative loop; whenw(e)>0, then there will be a path with sum of edge weights equals to
0 fromvitovj, a contradiction witheis a shortest path fromvitovj; whenw(e) = 0, then
we can always find another shortest path with weight 0 fromvitovjthat does not contain
e. It implies that for any pair verticesuandvifebelongs to one shortest path fromuto
v, then we can always replaceewithpsuch that another shortest path fromutovdoes not
containe, thusewill not be very useful.
If the edgee= (vi, vj) itself is the only shortest path fromvitovj, thenewill be very useful
since for pair of verticesviandvj, edgeebelongs to every shortest path fromvitovj.
Thus an edgee= (vi, vj) is very useful if and only if the edge itself is the only shortest path
fromvitovj.
We use the Floyd-Warshall algorithm to compute the shortest path lengthopt(i, j, k) of any
pair of verticesvi, vj, and a edge (vi, vj) is very useful if and only ifopt(i, j,0) =opt(i, j, n)
andopt(i, j,0)< opt(i, k, n) +opt(k, j, n) for all 1knandk=i, j. Since Floyd-Warshall
algorithm has complexityO(n^3 ), and for each edge, it needO(n) to check if the edge is very
useful, since the number of edges isO(n^2 ), thus the algorithm runs inO(n^3 +n^3 ) =O(n^3 ).