# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## Floyd-Warshall Algorithm Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Floyd Warshall's Algorithm is used for solving .....

All pair shortest path problems | |

Single Source shortest path problems | |

Network flow problems | |

Sorting problems |

Question 1 Explanation:

Floyd Warshall's Algorithm is used for solving all pair shortest path problems. It means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Floyd Warshall's Algorithm can be applied on .....

Undirected and unweighted graphs | |

Undirected graphs | |

Directed graphs | |

Acyclic graphs |

Question 2 Explanation:

Floyd Warshall Algorithm can be applied in directed graphs. From a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the Floyd Warshall Algorithm.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the running time of the Floyd Warshall Algorithm?

Big-oh(V) | |

Theta(V ^{2}) | |

Big-Oh(VE) | |

Theta(V ^{3}) |

Question 3 Explanation:

The running time of the Floyd Warshall algorithm is determined by the triply nested for loops. Since each execution of the for loop takes O(1) time, the algorithm runs in time Theta(V

^{3}).Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What approach is being followed in Floyd Warshall Algorithm?

Greedy technique | |

Dynamic Programming | |

Linear Programming | |

Backtracking |

Question 4 Explanation:

Floyd Warshall Algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Floyd Warshall Algorithm can be used for finding .....

Single source shortest path | |

Topological sort | |

Minimum spanning tree | |

Transitive closure |

Question 5 Explanation:

One of the ways to compute the transitive closure of a graph in Theta(N

^{3}) time is to assign a weight of 1 to each edge of E and then run the Floyd Warshall Algorithm. There are 5 questions to complete.