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(V log V)
O(V^3)
O(E log V)
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
All vertices have the same in-degree and out-degree.
The graph is strongly connected.
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.
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
The graph is planar.
Every vertex has a degree of at least 2.
The number of vertices is greater than or equal to 3.
The graph is connected.
How does A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It discards all previously explored paths and focuses only on the new path.
It updates the cost of the node and re-evaluates its neighbors.
It ignores the new path, as it already explored that node.
It backtracks to the start node and restarts the search.
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 maximum number of friendships in the network.
The maximum number of users who are not friends with each other.
The minimum number of groups that can be formed where no two friends are in the same group.
How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It ignores negative weight cycles and finds the shortest path regardless.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
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 ignores the new path and continues with the existing path.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It reweights the edges using a shortest path potential function.
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It adds a large constant to all edge weights to make them positive.
It removes all negative edges from the graph.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V - 1
E
V
E - 1
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 monotonic, meaning it always increases as the search gets closer to the goal.
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
Both admissible and consistent.