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.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Sparse graphs with negative edge weights
Dense graphs with positive edge weights
Unweighted graphs
Directed acyclic graphs (DAGs)
In the context of shortest path algorithms, what is 'relaxation'?
Removing edges that cannot contribute to the shortest path.
Transforming a directed graph into an undirected graph.
Reducing the priority of a node in the priority queue.
Updating the distance to a node if a shorter path is found.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Stack
Queue
Binary heap
Linked list
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
A* Search
Bellman-Ford Algorithm
Depth First Search
Breadth First Search
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^3)
O(E log V)
O(V log V)
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It allows the algorithm to handle negative edge weights.
It improves the time complexity for sparse graphs.
It reduces the space complexity of the algorithm.
It simplifies the implementation of the algorithm.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E
E - 1
V - 1
V
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It is more efficient for sparse graphs.
It only requires a single source vertex as input.
It can handle graphs with negative edge weights.
It can detect negative weight 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/2
n - 1
1
n