What is the primary advantage of using the Floyd-Warshall algorithm over Dijkstra's algorithm for finding shortest paths in a graph?
It can detect negative weight cycles.
It only requires a single source vertex as input.
It is more efficient for sparse graphs.
It can handle graphs with negative edge weights.
How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It restarts the search from the start node with the updated information.
It marks the node as visited and does not consider it again.
It updates the cost of the node and re-evaluates its neighbors.
It ignores the new path and continues with the existing path.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Reweighting edges using a potential function
Dynamic programming
Greedy edge relaxation
Divide and conquer approach
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Adding an edge between two vertices with different colors.
Adding a new vertex and connecting it to an existing vertex.
Adding a new vertex and connecting it to all existing vertices.
Removing an edge between two vertices with the same color.
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 everyone knows each other within a group.
The minimum number of groups that can be formed where no two friends are in the same group.
The maximum number of friendships in the network.
The maximum number of users who are not friends with each other.
In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(V^3)
O(V log V)
O(E log V)
O(V^2)
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.
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
The graph has no cycles.
All vertices have the same in-degree and out-degree.
The graph is strongly connected.
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.
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
1
n - 1
What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?
O(V + E), where V is the number of vertices and E is the number of edges
O(E log V), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
It depends on the heuristic function and can be exponential in the worst case.