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

Dark Mode

Bikram
asked
in Algorithms
Oct 4, 2016

210 views
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 |

- i - c, ii - d, iii - a, iv - b
- i - d, ii - a, iii - c, iv - b
- i - b, ii - d, iii - a, iv - c
- i - d, ii - b, iii - a, iv - c

5 votes

Best answer

**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 .