Consider the following problem:

You are given an undirected graph G with n vertices and m edges, along with a source vertex s. You want to find the shortest paths from s to all other vertices in G. You decide to use Dijkstra's algorithm, but with a twist: you only want to explore a subset of the vertices in G. Specifically, you only want to explore the vertices whose indices are prime numbers.

Which of the following statements is true about the running time of this modified Dijkstra's algorithm?

A) The running time is O(m log n) in the worst case.

B) The running time is O(n^2) in the worst case.

C) The running time is O(n log log n) in the worst case.

D) The running time is O(m + n log log n) in the worst case.

Note: The prime number sieve used in this problem has a time complexity of O(n log log n).

Answer rating: 100% (QA)

The detailed answer for the above question is provided below The correct answer is option D The runn... View the full answer