search
Log In
3 votes
930 views

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)$
in Algorithms
recategorized
930 views

1 Answer

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

C is answer
Answer:

Related questions

5 votes
1 answer
1
2.4k views
Let $n=4$ and $(a_1, a_2, a_3, a_4)$=(do, if, int, while). Let $p(1:4)=\bigg (\dfrac{3}{8}, \dfrac{3}{8}, \dfrac{1}{8}, \dfrac{1}{8} \bigg)$ ... $q(i)$ denotes the probability with which we search $a_i$ and the identifier $x$ being searched satisfy $a_i < x < a_{i+1}$ respectively. The optimal search tree is given by:
asked Aug 9, 2016 in Algorithms jothee 2.4k views
2 votes
1 answer
2
861 views
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
asked Aug 9, 2016 in Algorithms jothee 861 views
2 votes
1 answer
3
1.7k views
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))$
asked Aug 9, 2016 in Algorithms jothee 1.7k views
4 votes
3 answers
4
2.3k views
Given two sequences $X$ and $Y$: $X=\langle a, b, c, b, d, a, b \rangle$ $Y=\langle b, d, c, a, b, a \rangle$ The longest common subsequence of X and Y is: $\langle b, c, a \rangle$ $\langle c, a, b \rangle$ $\langle b, c, a, a \rangle$ $\langle b, c, b, a \rangle$
asked Aug 9, 2016 in Algorithms jothee 2.3k views
...