IDRASAcademic OS
Unit 2: Graph Algorithms: Traversals, Shortest Paths & Spanning Trees 35 mins study timeADVANCED

Graph Traversals (BFS, DFS) & Dijkstra's Single-Source Shortest Path Algorithm

Graph topology modeling, adjacency lists vs matrices, queue-based BFS, stack-based DFS, and greedy priority-queue Dijkstra relaxation.

Verified: Faculty Peer Review Board

Learning Objectives

    Essential Prerequisites

      Layer 1: Intuition & Why It Matters

      The Core Mental Model

      “Graph ka matlab hota hai interconnected nodes (Jaise cities) aur unke beech ke raste (Edges / Roads). Google Maps sochiye: Aapko Delhi se Mumbai jana hai, beech me kayi raste hain (Jaipur, Agra, Udaipur, etc.). Sabse chhota rasta kaise milega? Dijkstra ka Algorithm: 1. Delhi ka distance 0 maan liya, baaki saari cities ka distance infinity (∞). 2. Min-Heap (Priority Queue) me daliye. 3. Delhi se nikalke Jaipur aur Agra ka distance check kiya: Delhi->Jaipur = 250km, Delhi->Agra = 200km. 4. Sabse kam distance (Agra) ko pehle pick karo, wahan se aage ke raste explore karo. 5. Is process ko "Edge Relaxation" kehte hain: Agar naya rasta purane raste se chhota hai, to record update kar do!”

      Why This Exists

      Google Maps navigation, Swiggy/Zomato delivery routing, aur internet router BGP/OSPF protocol poore ke poore graph shortest path algorithms par chalte hain.

      Beginner Foundation

      Graph ka matlab hota hai interconnected nodes (Jaise cities) aur unke beech ke raste (Edges / Roads). Google Maps sochiye: Aapko Delhi se Mumbai jana hai, beech me kayi raste hain (Jaipur, Agra, Udaipur, etc.). Sabse chhota rasta kaise milega? Dijkstra ka Algorithm: 1. Delhi ka distance 0 maan liya, baaki saari cities ka distance infinity (∞). 2. ...

      Micro Concepts Decomposition

      MICRO CONCEPT 1Canonical Object

      Adjacency Representations & Traversal Frontiers

      Adjacency list uses O(V + E) space. BFS explores radial rings via FIFO Queue; DFS explores depth via LIFO Stack.

      Key Takeaway: BFS discovers unweighted shortest paths; DFS discovers topological sorts and connected components.
      MICRO CONCEPT 2Canonical Object

      Dijkstra's Greedy Edge Relaxation

      Distance updates d(v) = min(d(v), d(u) + w(u,v)) using a min-heap priority queue guarantees optimal paths for non-negative weights.

      Key Takeaway: Min-heap Dijkstra achieves O((V + E) log V) running time, preventing exhaustive exponential path enumeration.
      Layer 3 & 4: Formal Specification & Mechanism

      Hardware State Machine Architecture

      Let G = (V, E) be a directed, weighted graph with non-negative edge weight function w: E -> R+ U {0}. Dijkstra maintains: 1. S: set of vertices whose final shortest-path weights from source s have been determined. 2. Q = V \ S: min-priority queue keyed by d values. Relaxation Step: RELAX(u, v, w): if d[v] > d[u] + w(u, v): d[v] = d[u] + w(u, v) π[v] = u DECREASE_KEY(Q, v, d[v]) Complexity: - Array implementation: O(V^2 + E) = O(V^2). - Binary min-heap implementation: O((V + E) log V). - Fibonacci heap implementation: O(V log V + E).
      1. Initialize distance array with infinity; set source distance to 0. 2. Push (0, source) into min-heap priority queue. 3. While queue is not empty, pop element with minimum distance. 4. If popped distance > recorded distance, skip (stale heap entry). 5. Iterate outgoing edges and relax adjacent nodes, pushing updated distances to heap.
      Layer 7: Interactive Laboratory

      Interactive Simulator

      DSA • SIMULATIONGraph Traversal & Dijkstra Shortest Path Laboratory
      Launch Fullscreen Lab
      DSA / ADA • GRAPH ALGORITHMSShortest Path & Traversals

      Graph Traversal & Dijkstra Shortest Path Laboratory

      Start Node:
      Step 1 of 7
      4215810263ABCDEF
      State Transition

      Initialize Dijkstra: dist[A] = 0, all others = ∞.

      Dijkstra Shortest Distance Vectorfrom source A
      A
      0
      B
      ∞
      C
      ∞
      D
      ∞
      E
      ∞
      F
      ∞
      Layer 5: Step-by-Step Worked Numerical Example

      End-to-End Execution Trace

      Graph: A->B (4), A->C (2), C->B (1), B->D (5). Start at A: d[A]=0, others=inf. Pop A: Relax B (d=4), relax C (d=2). Heap: [(2,C), (4,B)]. Pop C: Path A->C->B gives 2 + 1 = 3 < 4! Relax B to 3! Heap: [(3,B), (4,B)]. Pop B (d=3): Relax D to 3 + 5 = 8. Shortest paths: A=0, C=2, B=3, D=8.
      Layer 6: Active Runtime CodeLab

      Step-by-Step Code Execution (PYTHON)

      SQL Studio
      Font
      main.pyGlacier Light
      Ln 1 • Python 3.12
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      476 chars • 17 lines • Ln 1UTF-8 • 4 Spaces
      Interactive Terminal Shell

      Sandbox Terminal Ready

      Click Run Code or press Ctrl+Enter to compile and execute.

      ⚡ AURXON Bitstream Runtime v4.8IDRAS Academic Virtual Node
      Layer 8: Practice & Knowledge Verification

      Active Assessment Quiz

      No Practice Questions Configured

      Questions for this topic are currently undergoing faculty review.

      Academic Evaluation Preparation

      Viva Examination & University Scoring Strategy

      Standard Viva Examination Questions

      How to Write High-Scoring University Exam Answers

      Write the formal pseudocode for Dijkstra's algorithm, trace execution with an example weighted graph showing priority queue states at each step, prove correctness using induction on the shortest path invariant, and analyze time and space complexity with binary heap.