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
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Only Bellman-Ford algorithm
Both Dijkstra's and Bellman-Ford algorithm
Only Dijkstra's algorithm
Neither algorithm can find the shortest path
What is the purpose of the heuristic function in the A* search algorithm?
To store the visited nodes to avoid cycles.
To estimate the cost of the cheapest path from the current node to the goal node.
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.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Reweighting edges using a potential function
Greedy edge relaxation
Divide and conquer approach
Dynamic programming
What is the relationship between A* search and Dijkstra's algorithm?
A* is a generalization of Dijkstra's algorithm.
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
In A* search, what does the heuristic function estimate?
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
The number of nodes that are yet to be explored
The depth of the current node in the search tree
How does A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It backtracks to the start node and restarts the search.
It discards all previously explored paths and focuses only on the new path.
It ignores the new path, as it already explored that node.
It updates the cost of the node and re-evaluates its neighbors.
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
n - 1
1
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.
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
Infinity if there is no path from the vertex to itself.
The number of edges in the shortest path from a vertex to itself.
The shortest distance from a vertex to itself.
The shortest distance from the source vertex to that vertex.