Practice Exam

Question 1: What is the primary feature of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

Question 2: How does the Bellman-Ford algorithm handle negative weight cycles in the graph?

Question 3: What is the time complexity of the Bellman-Ford algorithm?

Question 4: In which scenario might you prefer to use the Bellman-Ford algorithm over Dijkstra’s algorithm?

A) When you have a dense graph with all positive weights.
B) When the graph contains negative weight edges and you need to verify the presence of negative weight cycles.
C) When you need the absolute fastest algorithm for all types of graphs.
D) When the graph is large and mostly unconnected.

Question 5: After how many iterations of edge relaxations does the Bellman-Ford algorithm conclude in a graph with 𝑛n vertices?

Question 6: What is the purpose of the additional iteration in the Bellman-Ford algorithm after the initial ∣𝑉∣−1∣V∣−1 iterations?

Question 7: Which of the following best describes the space complexity of the Bellman-Ford algorithm?

Question 1: What data structure is commonly used in the implementation of Dijkstra's algorithm to achieve optimal efficiency?

Question 2: Which of the following statements is true regarding Dijkstra’s algorithm?

Question 3: What is the time complexity of Dijkstra’s algorithm using a binary heap (priority queue)?

Question 4: Dijkstra's algorithm is terminated when which of the following conditions is met?

Question 5: In which scenario is it most suitable to use Dijkstra's algorithm over the Bellman-Ford algorithm?

A) When the graph contains negative weight edges.
B) When you need to find the shortest path in a graph with non-negative edge weights.
C) When you need to detect negative weight cycles.
D) When you are working with an unweighted graph.

Question 6: Which of the following problems can be effectively solved by Dijkstra’s algorithm?

Question 7: How does Dijkstra’s algorithm ensure that the shortest path to a vertex is found before moving on to the next vertex?

A) By relaxing all edges in a breadth-first manner.
B) By always choosing the vertex with the smallest known distance from the source next.
C) By rechecking all paths at the end of execution.
D) By processing vertices in alphabetical order.

Question 1: What does the Floyd-Warshall algorithm primarily compute?

Question 2: Which of the following statements is true about the Floyd-Warshall algorithm?

A) It can only be used with positive edge weights.
B) It updates its estimates based on relaxation of edges like Dijkstra's algorithm.
C) It detects negative weight cycles by checking diagonal elements in the distance matrix.
D) It requires more space than Dijkstra’s algorithm for all pairs shortest path.

Question 3: What is the time complexity of the Floyd-Warshall algorithm?

Question 4: What type of graph data structure is the Floyd-Warshall algorithm typically implemented on?

Question 5: In the Floyd-Warshall algorithm, how is the matrix dist[][] initially filled out?

A) dist[i][i] is set to infinity for all i.
B) dist[i][j] is set to 0 if there is an edge between i and j.
C) dist[i][j] is set to the weight of the edge (i, j) if it exists, otherwise infinity.
D) dist[i][j] is set to 1 for all pairs of vertices.

Question 6: How does the Floyd-Warshall algorithm handle negative weight cycles?

A) It fails to terminate when a negative weight cycle is present.
B) It terminates and returns the shortest path including the cycle.
C) It can detect cycles by finding negative values on the diagonal of the distance matrix after completion.
D) It ignores all negative weight edges to avoid cycles.

Question 7: Which of the following scenarios is ideal for using the Floyd-Warshall algorithm?

A) When you need the shortest path from a single source to a single destination.
B) When you need the shortest paths between every pair of vertices in a dense graph.
C) When the graph contains only positive cycles.
D) When you are dealing with an extremely large sparse graph.