Question

1. Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
Option 1 : Dynamic programming
Option 2 : Backtracking
Option 3 : Greedy
Option 4 : Divide & Conquer​

Answer 1

Answer:

The algorithm design technique that is used in finding all pairs of shortest distances in a graph is Dynamic Programming.

Dynamic Programming is a classical example of solving a complex problem by breaking the problem into small subproblems and storing the solutions in the memory by using data structures like arrays, trees etc.

It uses recursive techniques to find out an optimal solution at the end.

Answer 2

ANSWER:

Dynamic Programming is the algorithm design technique that finds shortest distances between all the pairs of vertices in a graph.

EXPLANATION:

• Dynamic Programming Technique uses Flyod Warshal Algorithm, where all pairs of shortest distance in a graph could be found.
• The algorithm is executed and weight of each pairs of vertices is been found individually.
• Then the weights are being summed up.
• If it does not give the details of paths, then the paths are being reconstructed with simple modifications.