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 is the purpose of the priority queue in Dijkstra's algorithm?

Accepted Answer

To maintain a list of unvisited nodes

Answer

To track visited nodes

Answer

To store distances to all nodes

Answer

To find the shortest path from the source to all other nodes

Question 9

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 10

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 11

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 12

which of the below is not an application of minimum spanning trees?

Accepted Answer

Searching algorithms

Answer

Network Design

Answer

Clustering

Answer

Image segmentation

Question 13

What is the underlying data structure used in Dijkstra's algorithm?

Accepted Answer

Min-Heap

Answer

Queue

Answer

Stack

Answer

Tree

Question 14

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 15

What is the central idea behind Dijkstra's algorithm?

Accepted Answer

Iteratively choose the vertex with the shortest distance from the starting vertex and add it to the shortest path

Answer

Recursively explore all possible paths from the starting vertex to find the shortest one

Answer

Apply dynamic programming to compute the shortest paths from the starting vertex to all other vertices

Answer

Use a greedy approach to add the next edge to the shortest path

Question 16

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 17

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 18

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

Accepted Answer

Priority queue

Answer

Queue

Answer

Stack

Answer

Linked list

Question 19

Identify a limitation of Kruskal's algorithm.

Accepted Answer

It is applicable only to undirected graphs.

Answer

It can handle graphs with negative edge weights.

Answer

It invariably produces the same spanning tree for a given graph.

Answer

It may not always find the minimum spanning tree.

Question 20

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 21

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 22

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 23

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 24

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 25

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 26

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 27

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 28

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 29

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 30

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 31

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 32

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 33

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 34

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 35

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 36

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 37

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 38

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 39

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 40

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 41

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 42

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 43

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 44

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 45

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 46

**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 47

**Enhanced for Precision**: In Prim's algorithm for finding an MST, which vertex is chosen as the initial vertex?

Accepted Answer

Any vertex with the lowest weight

Answer

The vertex with the lowest eccentricity

Answer

The vertex with the highest degree

Answer

The vertex that is most central in the graph

Question 48

**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 49

**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 50

**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 51

**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 52

**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