Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Bellman-Ford Algorithm
Breadth First Search
Depth First Search
A* Search
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is connected.
The graph is planar.
The number of vertices is greater than or equal to 3.
Every vertex has a degree of at least 2.
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
Both Dijkstra's and Bellman-Ford algorithm
Only Dijkstra's algorithm
Only Bellman-Ford algorithm
Which of the following data structures is commonly used to implement the priority queue in A* search?
Binary heap
Linked list
Stack
Queue
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 an edge between two vertices with different colors.
Adding a new vertex and connecting it to an existing vertex.
Removing an edge between two vertices with the same color.
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 detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It ignores negative weight cycles and finds the shortest path regardless.
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(E log V), where V is the number of vertices and E is the number of edges
It depends on the heuristic function and can be exponential in the worst case.
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
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It allows the algorithm to handle negative edge weights.
It reduces the space complexity of the algorithm.
It improves the time complexity for sparse graphs.
It simplifies the implementation of the algorithm.
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
Both admissible and consistent.
The heuristic must be consistent, meaning it satisfies the triangle inequality.
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It restarts the search from the start node with the updated information.
It marks the node as visited and does not consider it again.
It ignores the new path and continues with the existing path.
It updates the cost of the node and re-evaluates its neighbors.