What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
It depends on the heuristic function and can be exponential in the worst case.
O(E log V), where V is the number of vertices and E is the number of edges
O(V + E), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
In A* search, what does the heuristic function estimate?
The cost of the cheapest path from the current node to the goal node
The number of nodes that are yet to be explored
The depth of the current node in the search tree
The total cost of the path from the start node to the current node
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Both Dijkstra's and Bellman-Ford algorithm
Neither algorithm can find the shortest path
Only Bellman-Ford algorithm
Only Dijkstra's algorithm
In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(V log V)
O(V^3)
O(V^2)
O(E log V)
Which of the following scenarios would likely benefit most from using the A* search algorithm?
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.
Determining if a graph is connected.
Finding the shortest path in an unweighted, undirected graph.
Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
Dijkstra's algorithm and Bellman-Ford algorithm
Bellman-Ford algorithm and Floyd-Warshall algorithm
Depth-First Search and Breadth-First Search
A* search algorithm and Dijkstra's algorithm
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
All vertices have the same in-degree and out-degree.
The graph has no cycles.
At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
The graph is strongly connected.
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 estimate the cost of the cheapest path from the current node to the goal node.
To determine the order in which nodes are visited during the search.
To store the visited nodes to avoid cycles.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Linked list
Binary heap
Stack
Queue
What is the relationship between A* search and Dijkstra's algorithm?
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
A* is a generalization of Dijkstra's algorithm.
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.