In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E
V
E - 1
V - 1
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.
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)
Unweighted graphs
Sparse graphs with negative edge weights
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)?
1
n - 1
n
n/2
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 only be applied to problems in two-dimensional space.
It can be computationally expensive for large graphs with complex heuristics.
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(V^3)
O(E log V)
O(V^2)
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Depth First Search
Breadth First Search
Bellman-Ford Algorithm
A* Search
Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
A* search algorithm and Dijkstra's algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
Bellman-Ford algorithm and Floyd-Warshall algorithm
Depth-First Search and Breadth-First Search
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Adding a new vertex and connecting it to all existing vertices.
Removing an edge between two vertices with the same color.
Adding a new vertex and connecting it to an existing vertex.
Adding an edge between two vertices with different colors.
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(V + E), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
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