Question 2 2 pts Select all of the following which are true for single-source sh

Question

Question 2 2 pts Select all of the following which are true for single-source shortest paths in a strongly connected directed graph which has a cycle containing an edge with a negative weight. For any two vertices u and v, the shortest path from u to v has weight 0. Dijkstra's Algorithm will detect the existence of the cycle with a negative weight edge The Bellman-Ford algorithm will detect the existence of the cycle with a negative weight edge For any two vertices u and v, the shortest path from u to v has weight-oo.

Explanation / Answer

Option 1. Wrong: As there can be a negative weight edge in the directed graph, so shortest paths might have -ve weight as well.

Option 2: Wrong: Dijkstra Algorithm is greedy in nature and once a edge is visited its weight is taken into account and marked closed, its not visited again. But this won’t work for -ve weighted edges as reevaluation might be required once we find such edges.

Option 3: Correct: Bellman ford uses Dynamic programming has “memorization” feature which enable the recalculation of the weight of the path and traverse back if required. As its dynamic in nature it can handle -ve weighted edges as well.

Now in order to detect the -ve cycle weight of the graph- in bellman ford algorithm we take edges one by one. Hence after ith iteration the shortest path with i edges are calculated. Now if cycle dosen’t exists then there can be maximum V-1 edge in any simple path. But if we get an edge which when visited gives the shortest path, implies that there is existence of -ve weight cycle in the graph.

Option 4: Correct: As we discussed in case there is existence of -ve weight cycle. Once we enter -ve cycle   shortest path would be infinity in but in -ve direction i.e. -

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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