In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(E log V)
O(V^2)
O(V^3)
O(V log V)
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Breadth First Search
Bellman-Ford Algorithm
Depth First Search
A* Search
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
Cannot be determined
The graph cannot exist
Yes
Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
Bellman-Ford algorithm and Floyd-Warshall algorithm
Depth-First Search and Breadth-First Search
A* search algorithm and Dijkstra's algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
In a graph coloring problem, what scenario leads to the requirement of an additional color?
Removing an edge between two vertices with the same color.
Adding a new vertex and connecting it to all existing vertices.
Adding a new vertex and connecting it to an existing vertex.
Adding an edge between two vertices with different colors.
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Both Dijkstra's and Bellman-Ford algorithm
Only Dijkstra's algorithm
Only Bellman-Ford algorithm
Neither algorithm can find the shortest path
Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?
Every vertex has a degree of at least 2.
The graph is planar.
The graph is connected.
The number of vertices is greater than or equal to 3.
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 - 1
n/2
1
n
What is a potential drawback of using A* search in practice?
It always requires an admissible heuristic, which can be difficult to define.
It can only be applied to problems in two-dimensional space.
It can be computationally expensive for large graphs with complex heuristics.
It is not guaranteed to find a solution even if one exists.
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 shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.
The shortest distance from a vertex to itself.