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 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.
What is the purpose of the heuristic function in the A* search algorithm?
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 estimate the cost of the cheapest path from the current node to the goal node.
To store the visited nodes to avoid cycles.
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
1
n/2
n - 1
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Neither algorithm can find the shortest path
Only Dijkstra's algorithm
Only Bellman-Ford algorithm
Both Dijkstra's and Bellman-Ford algorithm
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It reweights the edges using a shortest path potential function.
It removes all negative edges from the graph.
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It adds a large constant to all edge weights to make them positive.
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
Cannot be determined
No
The graph cannot exist
Yes
What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?
O(V^2 * E)
O(V * E)
O(E^2 * V)
O(V + E)
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* and Dijkstra's algorithm are entirely unrelated.
Dijkstra's algorithm is a special case of A* search.
A* is a generalization of Dijkstra's algorithm.
What is a potential drawback of using A* search in practice?
It can be computationally expensive for large graphs with complex heuristics.
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 only be applied to problems in two-dimensional space.
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 handle graphs with negative edge weights.
It is more efficient for sparse graphs.
It can detect negative weight cycles.