An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
Cannot be determined
No
The graph cannot exist
Yes
In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The number of edges in the shortest path from a vertex to itself.
The shortest distance from a vertex to itself.
Infinity if there is no path from the vertex to itself.
The shortest distance from the source vertex to that vertex.
How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
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.
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.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Greedy edge relaxation
Reweighting edges using a potential function
Divide and conquer approach
Dynamic programming
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(E log V)
O(V^3)
O(V log V)
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V - 1
V
E
E - 1
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
Unweighted graphs
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
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.
All vertices have the same in-degree and out-degree.
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It simplifies the implementation of the algorithm.
It reduces the space complexity of the algorithm.
It allows the algorithm to handle negative edge weights.
It improves the time complexity for sparse graphs.
For the A* search algorithm to guarantee finding the shortest path, what condition must the heuristic function satisfy?
The heuristic must be admissible, meaning it never overestimates the cost to reach the goal.
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.
Both admissible and consistent.