In the context of shortest path algorithms, what is 'relaxation'?
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.
Updating the distance to a node if a shorter path is found.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Queue
Stack
Binary heap
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.
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
Both admissible and consistent.
The heuristic must be consistent, meaning it satisfies the triangle inequality.
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(E log V)
O(V^3)
O(V^2)
A graph representing a social network has users as vertices and friendships as edges. What does finding the chromatic number of this graph signify?
The minimum number of groups that can be formed where everyone knows each other within a group.
The maximum number of friendships in the network.
The minimum number of groups that can be formed where no two friends are in the same group.
The maximum number of users who are not friends with each other.
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The number of edges in the shortest path from a vertex to itself.
The shortest distance from the source vertex to that vertex.
The shortest distance from a vertex to itself.
Infinity if there is no path from the vertex to itself.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
The graph has no cycles.
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.
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It improves the time complexity for sparse graphs.
It simplifies the implementation of the algorithm.
It reduces the space complexity of the algorithm.
It allows the algorithm to handle negative edge weights.
How does A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It backtracks to the start node and restarts the search.
It discards all previously explored paths and focuses only on the new path.
It ignores the new path, as it already explored that node.
It updates the cost of the node and re-evaluates its neighbors.