Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
Dijkstra's algorithm and Bellman-Ford algorithm
Depth-First Search and Breadth-First Search
Bellman-Ford algorithm and Floyd-Warshall algorithm
A* search algorithm and Dijkstra's algorithm
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It improves the time complexity for sparse graphs.
It simplifies the implementation of the algorithm.
It allows the algorithm to handle negative edge weights.
It reduces the space complexity of the algorithm.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
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.
The graph is strongly connected.
All vertices have the same in-degree and out-degree.
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
Cannot be determined
The graph cannot exist
Yes
No
Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding the shortest path in an unweighted, undirected graph.
Determining if a graph is connected.
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.
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.
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 log V)
O(V^3)
In the context of shortest path algorithms, what is 'relaxation'?
Removing edges that cannot contribute to the shortest path.
Reducing the priority of a node in the priority queue.
Transforming a directed graph into an undirected graph.
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
Binary heap
Linked list
Queue
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Sparse graphs with negative edge weights
Directed acyclic graphs (DAGs)
Unweighted graphs