Master Minimum Spanning Trees and Shortest Paths: Interactive Learning Quizzes

Question 1

Which step in Dijkstra's algorithm involves updating the distance to a vertex if a shorter path is found?

Accepted Answer

Set distance to the new value if smaller

Answer

Initialize distances to infinity

Answer

Add vertex to the settled set

Answer

Choose the next vertex with the smallest distance

Question 2

What is the primary purpose of the Floyd-Warshall algorithm?

Accepted Answer

Finds all-pairs shortest paths

Answer

Finds minimum spanning trees

Answer

Finds shortest paths between two vertices

Answer

Finds cycles in a graph

Question 3

Which data structure plays a crucial role in Kruskal's algorithm for finding minimum spanning trees?

Accepted Answer

Disjoint-set data structure

Answer

Adjacency list

Answer

Adjacency matrix

Answer

Hash table

Question 4

In Bellman-Ford algorithm, what is the condition for relaxation, or updating the distance to a vertex?

Accepted Answer

New distance is smaller than the current distance

Answer

New distance is equal to the current distance

Answer

New distance is greater than the current distance

Answer

New distance is zero

Question 5

What does the presence of a negative cycle in a graph imply?

Accepted Answer

There is a path with negative total weight

Answer

The shortest path between two vertices does not exist

Answer

The graph is disconnected

Answer

The graph is acyclic

Question 6

Identify the step that is not part of Dijkstra's algorithm for finding the shortest path:

Accepted Answer

Adding nodes to the visited set in a specific order

Answer

Initializing all distances to infinity

Answer

Setting the source node's distance to 0

Answer

Relaxing edges

Question 7

What is a limitation of Prim's algorithm for finding minimum spanning trees?

Accepted Answer

It requires the graph to be connected.

Answer

It is more efficient than Kruskal's algorithm.

Answer

It is easier to implement than Kruskal's algorithm.

Answer

It is guaranteed to find the unique minimum spanning tree.

Question 8

What makes Bellman-Ford algorithm different from the Floyd-Warshall algorithm?

Accepted Answer

Bellman-Ford can handle negative weight edges, unlike Floyd-Warshall.

Answer

Floyd-Warshall can handle negative weight edges, unlike Bellman-Ford.

Answer

Bellman-Ford is more efficient than Floyd-Warshall.

Answer

Floyd-Warshall is more efficient than Bellman-Ford.

Question 9

The Floyd-Warshall algorithm is most suitable for finding shortest paths in what type of graph?

Accepted Answer

Dense graph

Answer

Sparse graph

Answer

Undirected graph

Answer

Directed graph

Question 10

Which of the following is a limitation of Prim's algorithm?

Accepted Answer

It may not always produce a unique MST

Answer

It can handle duplicate edge weights

Answer

It can handle graphs with negative edge weights

Answer

It is efficient for sparse graphs

Question 11

What is the time complexity of Floyd-Warshall algorithm?

Accepted Answer

O(V^3)

Answer

O(V)

Answer

O(V^2)

Answer

O(E log V)

Question 12

When dealing with graphs containing negative edge weights, how must the algorithms for finding minimum spanning trees and shortest paths be adjusted?

Accepted Answer

Modified versions of the algorithms and specialized data structures are needed to handle negative weights.

Answer

The algorithms can be used directly without any modifications.

Question 13

Which algorithm is suitable for finding the minimum spanning tree of a weighted, undirected graph?

Accepted Answer

Kruskal's algorithm

Answer

Breadth-first search

Answer

Dijkstra's algorithm

Answer

Bellman-Ford algorithm

Question 14

When implementing Prim's algorithm, which data structure is employed?

Accepted Answer

Priority queue

Answer

Queue

Answer

Stack

Answer

Linked list

Question 15

Which of the following is **NOT** an application of minimum spanning trees (MSTs)?

Accepted Answer

Finding the shortest path between two nodes

Answer

Clustering data points

Answer

Segmenting images

Answer

Designing communication networks

Question 16

What is the time complexity of Kruskal's algorithm for finding the MST?

Accepted Answer

O(E log V)

Answer

O(V log E)

Answer

O(V^2)

Answer

O(E^2)

Question 17

Which algorithm can be used to handle negative edge weights in finding the shortest path?

Accepted Answer

Bellman-Ford algorithm

Answer

A* algorithm

Answer

Floyd-Warshall algorithm

Answer

Dijkstra's algorithm without any modification

Question 18

What is the time complexity of the Floyd-Warshall algorithm for finding shortest paths between all pairs of vertices?

Accepted Answer

O(V^3)

Answer

O(V log V)

Answer

O(V^2)

Answer

O(E log V)

Question 19

In Prim's algorithm, what do we start with to construct the minimum spanning tree?

Accepted Answer

A single vertex and iteratively add edges

Answer

A complete graph and iteratively remove edges

Answer

A randomly chosen edge and iteratively add vertices

Answer

A randomly chosen vertex and iteratively add edges

Question 20

Which data structure efficiently supports the priority queue used in Dijkstra's algorithm to track distances to vertices?

Accepted Answer

Heap

Answer

Array

Answer

Linked list

Answer

Binary tree

Question 21

The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph using which technique?

Accepted Answer

Dynamic programming

Answer

Greedy approach

Answer

Divide-and-conquer strategy

Answer

Backtracking

Question 22

Dijkstra's algorithm has a time complexity of:

Accepted Answer

O(E log V)

Answer

O(V)

Answer

O(V^2)

Answer

O(E + V)

Question 23

What is the time complexity of the Floyd-Warshall algorithm?

Accepted Answer

O(V^3)

Answer

O(V^2)

Answer

O(E log V)

Answer

O(E + V)

Question 24

Besides finding shortest paths, what is another significant application of the Floyd-Warshall algorithm?

Accepted Answer

Transitive Closure

Answer

Minimum Spanning Tree

Answer

Strongly Connected Components

Answer

Eulerian Circuit

Question 25

In the context of network design, what makes minimum spanning trees (MSTs) particularly valuable?

Accepted Answer

Reducing network costs

Answer

Minimizing network delays

Answer

Increasing network bandwidth

Question 26

What is the time complexity of Kruskal's algorithm for finding the minimum spanning tree of a graph with 'V' vertices and 'E' edges?

Accepted Answer

O(E log V)

Answer

O(V + E)

Answer

O(V^2)

Question 27

Which algorithm is commonly used to find the shortest path between two vertices in a weighted, directed graph?

Accepted Answer

Dijkstra's algorithm

Answer

Prim's algorithm

Answer

Kruskal's algorithm

Question 28

Which algorithm efficiently finds all-pairs shortest paths in a weighted, directed graph?

Accepted Answer

Floyd-Warshall algorithm

Answer

Dijkstra's algorithm

Answer

Prim's algorithm

Answer

Kruskal's algorithm

Question 29

What is the time complexity of Floyd-Warshall algorithm for finding all-pairs shortest paths in a graph with 'V' vertices?

Accepted Answer

O(V^3)

Answer

O(V^2)

Answer

O(E log V)

Answer

O(V + E)

Question 30

Which data structure offers efficient operations for implementing a priority queue in Kruskal's algorithm?

Accepted Answer

Heap

Answer

Linked list

Answer

Stack

Answer

Queue

Question 31

Which data structure is employed in Kruskal's algorithm to manage disjoint sets?

Accepted Answer

Union-Find data structure

Answer

Queue

Answer

Stack

Answer

Heap

Question 32

Which algorithm effectively detects the presence of negative cycles in a weighted, directed graph?

Accepted Answer

Bellman-Ford algorithm

Answer

Kruskal's algorithm

Answer

Floyd-Warshall algorithm

Answer

Dijkstra's algorithm

Question 33

Which algorithm can be used to find the maximum spanning tree of a weighted, undirected graph?

Accepted Answer

Reverse Kruskal's algorithm

Answer

Dijkstra's algorithm

Answer

Prim's algorithm

Answer

Floyd-Warshall algorithm

Question 34

Which of the following is a defining characteristic of a minimum spanning tree?

Accepted Answer

It connects all nodes with the minimum possible total edge weight

Answer

It has the largest diameter

Answer

It includes the maximum number of edges

Question 35

In Dijkstra's algorithm, which data structure is utilized to manage the status of nodes (visited/unvisited)?

Accepted Answer

Priority queue

Answer

Linked list

Answer

Hash table

Answer

Stack

Question 36

Which algorithm is appropriate for determining the shortest path between every pair of nodes in a graph?

Accepted Answer

Floyd-Warshall algorithm

Answer

Dijkstra's algorithm

Answer

Prim's algorithm

Answer

Kruskal's algorithm

Question 37

In Prim's algorithm, what criterion guides the selection of the next edge to add to the spanning tree?

Accepted Answer

Lowest weight

Answer

Random selection

Answer

Depth-first search

Answer

Highest weight

Question 38

In Dijkstra's algorithm, what does the distance label associated with a node represent?

Accepted Answer

Shortest distance from the starting node

Answer

Number of hops from the starting node

Answer

Longest distance from the starting node

Answer

Edge weight of the incoming edge

Question 39

Which of the following is a potential drawback of Kruskal's algorithm?

Accepted Answer

Reduced efficiency with dense graphs

Answer

Guarantee of the optimal solution

Answer

Ease of implementation

Answer

Ability to handle negative edge weights

Question 40

What is the time complexity of Floyd-Warshall algorithm for an n-node graph?

Accepted Answer

O(n^3)

Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Question 41

**Rewritten for Enhanced Clarity**: What is the main objective of determining a minimum spanning tree (MST)?

Accepted Answer

To connect all vertices within a graph utilizing edges with the least cumulative weight

Answer

To quantify the number of cycles present within a graph

Answer

To determine the shortest path between two arbitrary vertices in a graph

Question 42

**Updated for Real-world Relevance**: Which scenario exemplifies a practical application of determining shortest paths?

Accepted Answer

Routing in computer networks

Answer

Detecting cycles in a graph

Answer

Determining the diameter of a graph

Answer

Finding the maximum flow in a network

Question 43

**Reformulated for Clarity**: What is the purpose of the Floyd-Warshall algorithm?

Accepted Answer

Finding all pairs of shortest paths in a weighted graph

Answer

Finding a minimum spanning tree in a weighted graph

Answer

Determining the diameter of a graph

Question 44

**Rewritten for Enhanced Clarity**: Which type of graph contains a cycle with negative weight?

Accepted Answer

A graph with an edge having a weight of -10

Answer

A graph with all negative edge weights

Answer

A graph with all positive edge weights

Answer

A graph with no negative edge weights

Question 45

**Rephrased for Clarity**: Which heuristic function is utilized in the A* search algorithm?

Accepted Answer

Estimated remaining distance to the goal

Answer

Number of vertices visited

Answer

Total distance traversed thus far

Answer

Degree of the current vertex

Question 46

**Rewritten for Accuracy**: What is a key advantage of using A* search versus Dijkstra's algorithm?

Accepted Answer

It may find a shorter path by leveraging a heuristic function

Answer

It is more efficient for large graphs

Answer

It guarantees finding the shortest path in all scenarios