Algorithm

4. (Extra) Give a simple example of a directed graph with negative weight edges for which Dijkstra's algorithm fails. Your example should have the following properties: (1) Your graph should contain no more than 4 vertices (preferably 3). (2) Your graph should have at least one negative weight edge. (3) Your graph should not contain any negative weight cycles. (a) In your example, what values does Dijkstra's algorithm give for the shortest ths? What are the correct values for the shortest paths? (b) What is the time complexity of the following algorithm? pa DIJKSTRA (G, w, s) mark s as 0 (d(s) -0) and all // other vertices as infinitive /l S is empty at beginning. S //will ultimately contains //vertices of final shortest-path II weights from s 1. INITIALIZE SINGLE-SOURCE (G, s) 2. S-0 3. Initialize heap Q i.e.,VIG] based on marked value 4. While Q is not empty do u ? EXTRACT MIN(Q) // Pull out new vertex // + means union 7. for each vertex v in Adjlu] do /Perform relaxation for each //vertex v adjacent to u // means that if d(v)>d(u)+w(u,v), them Relax (u, v, w) // assign d(v)?d(u)-w(u,v), and make l/ entering vertex of v to be u. Update Q. /l Those v's are not in S, will be waiting to be // put in S. the smallest marked one will be // next