How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It updates the cost of the node and re-evaluates its neighbors.
It restarts the search from the start node with the updated information.
It ignores the new path and continues with the existing path.
It marks the node as visited and does not consider it again.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Queue
Binary heap
Stack
Linked list
How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
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.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
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 a vertex to itself.
Infinity if there is no path from the vertex to itself.
The shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.
In the context of shortest path algorithms, what is 'relaxation'?
Removing edges that cannot contribute to the shortest path.
Updating the distance to a node if a shorter path is found.
Transforming a directed graph into an undirected graph.
Reducing the priority of a node in the priority queue.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It removes all negative edges from the graph.
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It reweights the edges using a shortest path potential function.
It adds a large constant to all edge weights to make them positive.
In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(V^2)
O(E log V)
O(V^3)
O(V log V)
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
n - 1
n/2
1
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
Cannot be determined
The graph cannot exist
Yes
In A* search, what does the heuristic function estimate?
The depth of the current node in the search tree
The cost of the cheapest path from the current node to the goal node
The total cost of the path from the start node to the current node
The number of nodes that are yet to be explored