Graph Algorithms Quiz - I

What is the main purpose of Dijkstra's Algorithm?

• To determine the minimum spanning tree of a graph

• To calculate the maximum flow in a network

• To find the shortest path between nodes in a graph.

• To sort elements in an array

Explain the difference between Breadth-First Search and Depth-First Search.

• Breadth-First Search explores branch by branch, while Depth-First Search explores level by level.

• Breadth-First Search explores in a zig-zag pattern, while Depth-First Search explores in a straight line.

• Breadth-First Search explores level by level, while Depth-First Search explores branch by branch.

• Breadth-First Search always finds the shortest path, while Depth-First Search finds the longest path.

How is a Minimum Spanning Tree different from a Shortest Path Tree?

• A Minimum Spanning Tree focuses on connecting all vertices with minimum total edge weight, while a Shortest Path Tree focuses on finding the shortest paths from a specific root vertex to all other vertices.

• A Minimum Spanning Tree focuses on finding the shortest paths between all vertices, while a Shortest Path Tree focuses on connecting all vertices with minimum total edge weight.

• A Minimum Spanning Tree is used in graph traversal algorithms, while a Shortest Path Tree is used in sorting algorithms.

• A Minimum Spanning Tree guarantees the shortest path between any two vertices, while a Shortest Path Tree guarantees the minimum total edge weight.

What is the significance of Topological Sorting in graph theory?

• Topological Sorting helps in ordering vertices in a DAG to schedule tasks, resolve dependencies, and optimize algorithms.

• Topological Sorting has no practical applications in computer science

• Topological Sorting is used for sorting elements in an array

• Topological Sorting is only applicable to cyclic graphs

When is Bellman-Ford Algorithm preferred over Dijkstra's Algorithm?

• When there are negative edge weights in the graph.

• When the graph is directed

• When the graph is unweighted

• When the graph is acyclic

Describe the key idea behind Floyd's Algorithm for all pairs shortest path.

• Floyd's Algorithm always finds the longest path between all pairs of vertices

• Floyd's Algorithm is based on Dijkstra's Algorithm

• Floyd's Algorithm only works for unweighted graphs

• Floyd's Algorithm finds the shortest path between all pairs of vertices in a weighted graph.

What problem does Johnson's Algorithm aim to solve in graph theory?

• Determining the minimum spanning tree of a graph

• Finding all-pairs shortest paths in a graph with negative edge weights

• Identifying the chromatic number of a graph

• Finding the maximum flow in a graph

How does Dijkstra's Algorithm handle negative edge weights in a graph?

• Dijkstra's Algorithm ignores negative edge weights

• Dijkstra's Algorithm treats negative edge weights as zero

• Dijkstra's Algorithm can convert negative edge weights to positive values

• Dijkstra's Algorithm cannot handle negative edge weights.

What is the time complexity of Breadth-First Search in a graph?

• O(1)

• O(V + E)

• O(log(V))

• O(V * E)

Explain the concept of relaxation in the context of graph algorithms.

• Relaxation is the process of increasing the distance values of vertices in graph algorithms.

• Relaxation is not a relevant concept in graph algorithms.

• Relaxation in graph algorithms is the process of updating the distance values of vertices to find the shortest path.

• Relaxation in graph algorithms involves removing edges from the graph.