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(V^2 * E)
O(E^2 * V)
O(V * E)
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 depth of the current node in the search tree
The number of nodes that are yet to be explored
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Dynamic programming
Divide and conquer approach
Greedy edge relaxation
Reweighting edges using a potential function
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 maximum number of users who are not friends with each other.
The maximum number of friendships in the network.
The minimum number of groups that can be formed where everyone knows each other within a group.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Bellman-Ford Algorithm
Depth First Search
Breadth First Search
A* Search
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.
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.
A* is a generalization of Dijkstra's algorithm.
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)?
1
n - 1
n/2
n
In the context of shortest path algorithms, what is 'relaxation'?
Transforming a directed graph into an undirected graph.
Reducing the priority of a node in the priority queue.
Removing edges that cannot contribute to the shortest path.
Updating the distance to a node if a shorter path is found.
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
A* search algorithm and Dijkstra's algorithm
Bellman-Ford algorithm and Floyd-Warshall algorithm
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E - 1
V - 1
V
E