If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Only Bellman-Ford algorithm
Only Dijkstra's algorithm
Both Dijkstra's and Bellman-Ford algorithm
Neither algorithm can find the shortest path
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.
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 ignores the new path and continues with the existing path.
It restarts the search from the start node with the updated information.
It updates the cost of the node and re-evaluates its neighbors.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Binary heap
Linked list
Queue
Stack
Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding all possible paths between two vertices in a graph.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.
Determining if a graph is connected.
Finding the shortest path in an unweighted, undirected graph.
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.
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.
A* is a generalization of Dijkstra's algorithm.
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)
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
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 has no cycles.
All vertices have the same in-degree and out-degree.
The graph is strongly connected.
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.
Adding a new vertex and connecting it to an existing vertex.
Removing an edge between two vertices with the same color.
Adding an edge between two vertices with different colors.
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.