TomoLink
TCS NQT GuideTCS NQT Coding Capability & AlgorithmsShortest Path Algorithms (Dijkstra and Prim's/Kruskal's Basics)

Shortest Path Algorithms (Dijkstra and Prim's/Kruskal's Basics)

Learn core concepts, essential formulas, and attempt practice questions designed on the latest TCS NQT testing patterns.

Key Concepts & Formulas

  • 1Dijkstra: Finds single-source shortest path on weighted graphs with non-negative edges.
  • 2Prim's & Kruskal's: Find Minimum Spanning Tree (MST) of weighted graphs.
  • 3Kruskal's sorts all edges and uses Disjoint Set Union (DSU) to avoid cycles.

TCS NQT Style Practice Questions

Practice Question 1

Dijkstra's algorithm fails for which graph types?

A) Graphs with negative edge weights
B) Directed graphs
C) Disconnected graphs
D) Dense graphs

Correct Answer: A) Graphs with negative edge weights

Step-by-step Solution: Dijkstra assumes paths only grow longer. Negative edges violate this, leading to incorrect distances.

Practice Question 2

Kruskal's algorithm selects edges in what order?

A) Sorted ascending by weight
B) Sorted descending by weight
C) Random order
D) BFS order

Correct Answer: A) Sorted ascending by weight

Step-by-step Solution: Kruskal's is a greedy algorithm. It sorts all edges by weight and inserts the smallest edges first (if they don't form cycles).

Study Pro-Tip

Use Prim's for dense graphs (many edges) and Kruskal's for sparse graphs.

Back to TCS NQT Coding Capability & Algorithms Master Guide
PreviousNext