Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
A* search algorithm and Dijkstra's algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
Bellman-Ford algorithm and Floyd-Warshall algorithm
Depth-First Search and Breadth-First Search
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
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.
Both admissible and consistent.
The heuristic must be monotonic, meaning it always increases as the search gets closer to the goal.
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.
Dijkstra's algorithm is a special case of A* search.
A* is a generalization of Dijkstra's algorithm.
How does A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It updates the cost of the node and re-evaluates its neighbors.
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.
What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?
O(V + E)
O(E^2 * V)
O(V^2 * E)
O(V * E)
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E
V
V - 1
E - 1
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It improves the time complexity for sparse graphs.
It reduces the space complexity of the algorithm.
It allows the algorithm to handle negative edge weights.
It simplifies the implementation of the algorithm.
Which of the following data structures is commonly used to implement the priority queue in A* search?
Stack
Queue
Linked list
Binary heap
What is the purpose of the heuristic function in the A* search algorithm?
To determine the order in which nodes are visited during the search.
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 estimate the cost of the cheapest path from the current node to the goal node.
A graph representing a social network has users as vertices and friendships as edges. What does finding the chromatic number of this graph signify?
The minimum number of groups that can be formed where no two friends are in the same group.
The minimum number of groups that can be formed where everyone knows each other within a group.
The maximum number of users who are not friends with each other.
The maximum number of friendships in the network.