An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
Cannot be determined
Yes
No
The graph cannot exist
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 is more efficient for sparse graphs.
It can handle graphs with negative edge weights.
It can detect negative weight cycles.
In A* search, what does the heuristic function estimate?
The depth of the current node in the search tree
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 cost of the cheapest path from the current node to the goal node
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 discards all previously explored paths and focuses only on the new path.
It updates the cost of the node and re-evaluates its neighbors.
It backtracks to the start node and restarts the search.
What is the purpose of the heuristic function in the A* search algorithm?
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 calculate the exact cost of the path from the start node to the current node.
To store the visited nodes to avoid cycles.
How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It marks the node as visited and does not consider it again.
It restarts the search from the start node with the updated information.
It ignores the new path and continues with the existing path.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It reweights the edges using a shortest path potential function.
It removes all negative edges from the graph.
It adds a large constant to all edge weights to make them positive.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V
V - 1
E
E - 1
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^2), where V is the number of vertices
O(V + E), where V is the number of vertices and E is the number of edges
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(V log V)
O(V^3)
O(E log V)