Register

UGC NET CSE | December 2015 | Part 3 | Question: 20

• recategorized
1,994 views
3 votes
3 votes

Floyd-Warshall algorithm utilizes _____ to solve the all-pairs shortest paths problem on a directed graph in ____ time

  1. Greedy algorithm, $\theta(V^3)$
  2. Greedy algorithm, $\theta(V^2 lgn)$
  3. Dynamic programming, $\theta(V^3)$
  4. Dynamic programming, $\theta(V^2 lgn)$
• recategorized
User Avatar

1 Answer

3 votes
3 votes
Floyd-Warshall algorithm dynamic approch takes Θ(n^3) time.

C is answer
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
2
go_editor asked Aug 9, 2016
1,898 views
UGC NET CSE | December 2015 | Part 3 | Question: 19
The solution of the reccurence relation $T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+O(n) & \text{ if } n> 80 \end{cases}$ is $O(\lg n)$ $O(n)$ $O(n \lg n)$ None of the above
The solution of the reccurence relation$T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+O(n) & \tex...
User Avatar
2 votes
2 votes
1 answer
3
go_editor asked Aug 9, 2016
4,327 views
UGC NET CSE | December 2015 | Part 3 | Question: 18
If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in $O(d \: n \: k)$ $O(d n^k)$ $O(d+n)k)$ $O(d(n+k))$
If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in$O(d \: n \: k)$$O(d n^k)$...
User Avatar
Link Copied!