Floyd-Warshall Algorithm Quiz

What is the Floyd-Warshall algorithm used for?

• Finding the shortest path in an unweighted graph

• Finding the shortest paths between all pairs of vertices in a weighted graph

• Finding the Minimum Spanning Tree of a graph

• Detecting cycles in a directed graph

What is the time complexity of the Floyd-Warshall algorithm for a graph with V vertices?

• O(V)

• O(VlogV)

• O(V^2)

• O(V^3)

Floyd-Warshall algorithm is based on which programming paradigm?

• Greedy Algorithm

• Divide and Conquer

• Dynamic Programming

• Backtracking

Which of the following graph representations is most suitable for the Floyd-Warshall algorithm?

• Adjacency List

• Adjacency Matrix

• Edge List

• Incidence Matrix

What is the main idea behind the Floyd-Warshall algorithm?

• It uses a priority queue to determine the shortest path

• It iteratively updates the shortest paths using an intermediate vertex

• It builds a spanning tree using the minimum edge weight

• It performs a depth-first search for shortest paths

In the Floyd-Warshall algorithm, if there is no edge between two vertices u and v, what should be their initial distance in the adjacency matrix?

• 0

• 1

• ∞ (Infinity)

• -1

If a graph has V vertices, how many times does the innermost loop of the Floyd-Warshall algorithm execute?

• O(V)

• O(V^2)

• O(V^3)

• O(V^4)

Which of the following algorithms can be used as an alternative to Floyd-Warshall for finding all-pairs shortest paths?

• Dijkstra’s Algorithm

• Kruskal’s Algorithm

• Prim’s Algorithm

• Bellman-Ford Algorithm

Which property of the shortest path does the Floyd-Warshall algorithm exploit?

• Greedy choice property

• Optimal substructure

• Backtracking property

• Divide and conquer