What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It reduces the space complexity of the algorithm.
It improves the time complexity for sparse graphs.
It allows the algorithm to handle negative edge weights.
It simplifies the implementation of the algorithm.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It removes all negative edges from the graph.
It adds a large constant to all edge weights to make them positive.
It reweights the edges using a shortest path potential function.
In the context of shortest path algorithms, what is 'relaxation'?
Updating the distance to a node if a shorter path is found.
Reducing the priority of a node in the priority queue.
Removing edges that cannot contribute to the shortest path.
Transforming a directed graph into an undirected graph.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
The graph is strongly connected.
The graph has no cycles.
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.
All vertices have the same in-degree and out-degree.
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.
A* is a generalization of Dijkstra's algorithm.
Dijkstra's algorithm is a special case of A* search.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E - 1
E
V - 1
V
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
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
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
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 can detect negative weight cycles.
It is more efficient for sparse graphs.
What is the purpose of the heuristic function in the A* search algorithm?
To store the visited nodes to avoid cycles.
To calculate the exact cost of the path from the start node to the current node.
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.
In A* search, what does the heuristic function estimate?
The depth of the current node in the search tree
The number of nodes that are yet to be explored
The cost of the cheapest path from the current node to the goal node
The total cost of the path from the start node to the current node