231 views

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 comment

edited by
Why only option $C$ is correct, why not option $D$ as both Dijkstra's Algorithm and Bellman Ford Algorithm are $\text{Greedy}$ algorithms and both are $\text{Single source shortest path}$ algorithm

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 .

by

Bellman ford is dynamic approach??
Yes