How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It restarts the search from the start node with the updated information.
It marks the node as visited and does not consider it again.
It updates the cost of the node and re-evaluates its neighbors.
It ignores the new path and continues with the existing path.
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.
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.
The graph has no cycles.
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
The heuristic must be consistent, meaning it satisfies the triangle inequality.
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
Both admissible and consistent.
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.
It ignores negative weight cycles and finds the shortest path regardless.
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 total cost of the path from the start node to the current node
The depth of the current node in the search tree
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
Every vertex has a degree of at least 2.
The graph is planar.
The graph is connected.
The number of vertices is greater than or equal to 3.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
Unweighted graphs
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It only requires a single source vertex as input.
It can detect negative weight cycles.
It is more efficient for sparse graphs.
It can handle graphs with negative edge weights.
In the context of shortest path algorithms, what is 'relaxation'?
Updating the distance to a node if a shorter path is found.
Reducing the priority of a node in the priority queue.
Transforming a directed graph into an undirected graph.
Removing edges that cannot contribute to the shortest path.
What is a potential drawback of using A* search in practice?
It is not guaranteed to find a solution even if one exists.
It always requires an admissible heuristic, which can be difficult to define.
It can be computationally expensive for large graphs with complex heuristics.
It can only be applied to problems in two-dimensional space.