Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding the shortest path in an unweighted, undirected graph.
Determining if a graph is connected.
Finding all possible paths between two vertices in a graph.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It reduces the space complexity of the algorithm.
It allows the algorithm to handle negative edge weights.
It simplifies the implementation of the algorithm.
It improves the time complexity for sparse graphs.
What is the relationship between A* search and Dijkstra's algorithm?
A* and Dijkstra's algorithm are entirely unrelated.
Dijkstra's algorithm is a special case of A* search.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
A* is a generalization of Dijkstra's algorithm.
How does A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It ignores the new path, as it already explored that node.
It updates the cost of the node and re-evaluates its neighbors.
It discards all previously explored paths and focuses only on the new path.
It backtracks to the start node and restarts the search.
What is the minimum number of edges that need to be removed from a complete graph with 'n' vertices to make it acyclic (i.e., having no cycles)?
n
1
n/2
n - 1
Which of the following data structures is commonly used to implement the priority queue in A* search?
Queue
Binary heap
Stack
Linked list
What is the purpose of the heuristic function in the A* search algorithm?
To calculate the exact cost of the path from the start node to the current node.
To store the visited nodes to avoid cycles.
To determine the order in which nodes are visited during the search.
To estimate the cost of the cheapest path from the current node to the goal node.
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.
Infinity if there is no path from the vertex to itself.
The shortest distance from a vertex to itself.
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It is more efficient for sparse graphs.
It can handle graphs with negative edge weights.
It only requires a single source vertex as input.
It can detect negative weight cycles.
What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?
O(V * E)
O(V^2 * E)
O(E^2 * V)
O(V + E)