In the context of the Floyd-Warshall algorithm, what does a diagonal element of the distance matrix represent after the algorithm has completed?
The shortest distance from the source vertex to that vertex.
The number of edges in the shortest path from a vertex to itself.
Infinity if there is no path from the vertex to itself.
The shortest distance from a vertex to itself.
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Only Bellman-Ford algorithm
Only Dijkstra's algorithm
Neither algorithm can find the shortest path
Both Dijkstra's and Bellman-Ford algorithm
What is a potential drawback of using A* search in practice?
It always requires an admissible heuristic, which can be difficult to define.
It is not guaranteed to find a solution even if one exists.
It can only be applied to problems in two-dimensional space.
It can be computationally expensive for large graphs with complex heuristics.
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
1
n
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 number of vertices is greater than or equal to 3.
The graph is connected.
The graph is planar.
How does the A* algorithm handle situations where a more promising path to a previously explored node is discovered?
It updates the cost of the node and re-evaluates its neighbors.
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 A* search handle situations where a newly discovered path to a node is cheaper than the previously known path?
It backtracks to the start node and restarts the search.
It discards all previously explored paths and focuses only on the new path.
It ignores the new path, as it already explored that node.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
A* Search
Bellman-Ford Algorithm
Depth First Search
Breadth First Search
In A* search, what does the heuristic function estimate?
The cost of the cheapest path from the current node to the goal node
The depth of the current node in the search tree
The number of nodes that are yet to be explored
The total cost of the path from the start node to the current node
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
E
V
V - 1
E - 1