4. (Extra) Give a simple example of a directed graph with negative weight edges

Question

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

Explanation / Answer

lets take a graph with three vertices {A,B,C} withe edge weigts as follows:

(A,B,7)

(A,C,3)

(B,C,-12)

So starting :

the shortest distance between A to B = 7 and A to C is 3 according to the dijkstra's algorithm

but the shortest distance to reach C from A will be -5 because the shortest distance between A to B is 7 and shortest distance between B to C is -12 hence shortest distance to reach C from A will be 7+(-12) = -5

Hence we can say that dijkstra's algorithm will fail if there are any negative edges in a graph.

b.

Dijkstra's shortest path algorithm is O(ElogV) where:

Because Every vertex can be connected to every other V-1 vertices, so the number of adjacent edges to each vertex will be v-1 and finding and updating every adjacent vertex weight in min heap will be O(log(V))

hence time complexity will be O(E.log(V))

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.