How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.
It ignores negative weight cycles and finds the shortest path regardless.
In the worst case, how many iterations does the Bellman-Ford algorithm need to guarantee finding the shortest path?
V
E - 1
E
V - 1
Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
Dijkstra's algorithm and Bellman-Ford algorithm
Depth-First Search and Breadth-First Search
Bellman-Ford algorithm and Floyd-Warshall algorithm
A* search algorithm and Dijkstra's algorithm
Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding the shortest path in an unweighted, undirected graph.
Determining if a graph is connected.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.
Finding all possible paths between two vertices in a graph.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Unweighted graphs
Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
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
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Depth First Search
Bellman-Ford Algorithm
A* Search
Breadth First Search
What is the purpose of the heuristic function in the A* search algorithm?
To estimate the cost of the cheapest path from the current node to the goal node.
To calculate the exact cost of the path from the start node to the current node.
To determine the order in which nodes are visited during the search.
To store the visited nodes to avoid cycles.
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.
Infinity if there is no path from the vertex to itself.
The number of edges in the shortest path from a vertex to itself.
The shortest distance from a vertex to itself.
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
Cannot be determined
Yes
The graph cannot exist