433 views
2 votes
2 votes

Match the following
 

i.

Dijkstra's Algorithm

a. All pairs shortest path
ii. Bellman Ford Algorithm b. Greedy
iii. Floyd-Warshall Algorithm c. Reweighting
iv. Johnson Algorithm d. Single source  shortest path
  1. i - c, ii - d, iii - a, iv - b
  2. i - d, ii - a, iii - c, iv - b
  3. i - b, ii - d, iii - a, iv - c
  4. i - d, ii - b, iii - a, iv - c

1 Answer

Best answer
5 votes
5 votes

Answer C). 

Dijkstra's Algorithm --> Greedy and DP, Single source shortest path (May not work with negative edges)

Bellman Ford Algorithm --> DP and Single source shortest path  (Used for negative weights)

Floyd-Warshall Algorithm --> All pairs shortest path

Johnson Algorithm --> Reweighting done by bellman ford .

selected by
Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked Oct 4, 2016
345 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
3 votes
3 votes
1 answer
4
Bikram asked Oct 4, 2016
500 views
Maximum element in a min-heap represented by an array, can be computed in _____ time$O(n)$$O(\log n)$$O(n \log n)$ but not $O(n)$$O(1)$