QuizzesIntroduction to Graph Algorithms: Shortest Path and Minimum Spanning Tree
beginner
dsa

Introduction to Graph Algorithms: Shortest Path and Minimum Spanning Tree

A beginner-level quiz on understanding shortest path and minimum spanning tree algorithms in graph theory.

15 minutes 15 questions Pass at 70%
Time Limit
15 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

Questions in this quiz

15 questions on Introduction to Graph Algorithms: Shortest Path and Minimum Spanning Tree. Work through them here, then start the quiz to answer them and see your score.

  1. 1.What is the primary goal of Dijkstra's algorithm?

    • ATo find the shortest path from a single source to all vertices
    • BTo find the minimum spanning tree of a graph
    • CTo detect cycles in a graph
    • DTo sort the vertices of a graph
  2. 2.Which of the following algorithms is used to find a minimum spanning tree?

    • AKruskal's algorithm
    • BDijkstra's algorithm
    • CFloyd-Warshall algorithm
    • DBellman-Ford algorithm
  3. 3.In a graph with negative edge weights, which algorithm can be used to find the shortest path?

    • ADijkstra's algorithm
    • BBellman-Ford algorithm
    • CKruskal's algorithm
    • DPrim's algorithm
  4. 4.What is the time complexity of Dijkstra's algorithm using a priority queue?

    • AO(E log V)
    • BO(V^2)
    • CO(E^2)
    • DO(V log V)
  5. 5.Which data structure is commonly used in Prim's algorithm to select the minimum weight edge?

    • AStack
    • BHash Table
    • CQueue
    • DPriority Queue
  6. 6.What is the main difference between Prim's and Kruskal's algorithms?

    • APrim's works on directed graphs, Kruskal's on undirected
    • BPrim's is faster than Kruskal's
    • CPrim's uses a stack, Kruskal's uses a queue
    • DPrim's grows a single tree, Kruskal's grows a forest
  7. 7.Which algorithm can be used to detect negative weight cycles in a graph?

    • AKruskal's algorithm
    • BPrim's algorithm
    • CBellman-Ford algorithm
    • DDijkstra's algorithm
  8. 8.What is the purpose of a minimum spanning tree?

    • ATo find the shortest path between two vertices
    • BTo connect all vertices with the maximum total edge weight
    • CTo detect cycles in a graph
    • DTo connect all vertices with the minimum total edge weight
  9. 9.Which of the following is true about Dijkstra's algorithm?

    • AIt is a greedy algorithm
    • BIt works with graphs with negative weights
    • CIt finds the longest path in a graph
    • DIt uses a stack to find the shortest path
  10. 10.In Kruskal's algorithm, what is the first step?

    • ASort all edges in non-decreasing order of their weight
    • BFind the shortest path
    • CSelect a random vertex
    • DInitialize a priority queue
  11. 11.What is the time complexity of Kruskal's algorithm?

    • AO(E log E)
    • BO(V log V)
    • CO(E log V)
    • DO(V^2)
  12. 12.Which algorithm is more suitable for dense graphs when finding a minimum spanning tree?

    • ABellman-Ford algorithm
    • BDijkstra's algorithm
    • CKruskal's algorithm
    • DPrim's algorithm
  13. 13.What is a key characteristic of a spanning tree?

    • AIt is a directed graph
    • BIt contains cycles
    • CIt has the maximum number of edges
    • DIt includes all vertices of the graph
  14. 14.Which algorithm uses a union-find data structure to detect cycles?

    • APrim's algorithm
    • BDijkstra's algorithm
    • CFloyd-Warshall algorithm
    • DKruskal's algorithm
  15. 15.What is the primary application of the Floyd-Warshall algorithm?

    • ASorting vertices of a graph
    • BDetecting cycles in a graph
    • CFinding the shortest path between all pairs of vertices
    • DFinding the minimum spanning tree