In the context of shortest path algorithms, what is 'relaxation'?
Updating the distance to a node if a shorter path is found.
Transforming a directed graph into an undirected graph.
Removing edges that cannot contribute to the shortest path.
Reducing the priority of a node in the priority queue.
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
The graph cannot exist
Yes
No
Cannot be determined
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Unweighted graphs
Sparse graphs with negative edge weights
Directed acyclic graphs (DAGs)
Dense graphs with positive edge weights
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
Both admissible and consistent.
The heuristic must be consistent, meaning it satisfies the triangle inequality.
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It can handle graphs with negative edge weights.
It only requires a single source vertex as input.
It can detect negative weight cycles.
It is more efficient for sparse graphs.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Depth First Search
Bellman-Ford Algorithm
Breadth First Search
A* Search
In A* search, what does the heuristic function estimate?
The number of nodes that are yet to be explored
The total cost of the path from the start node to the current node
The cost of the cheapest path from the current node to the goal node
The depth of the current node in the search tree
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V - 1
V
E - 1
E
What is a potential drawback of using A* search in practice?
It can be computationally expensive for large graphs with complex heuristics.
It can only be applied to problems in two-dimensional space.
It always requires an admissible heuristic, which can be difficult to define.
It is not guaranteed to find a solution even if one exists.
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It simplifies the implementation of the algorithm.
It improves the time complexity for sparse graphs.
It allows the algorithm to handle negative edge weights.
It reduces the space complexity of the algorithm.