This lesson on Graph Algorithms (Dijkstra, Topological Sort) is hands-on and example-driven. You will trace and implement Dijkstra's algorithm to find the single-source shortest paths across non-negative weighted directed graphs. You will maintain distance tracking tables, perform iterative edge relaxation, and optimize path search performance using priority queues.

What You'll Be Able To Do

• Initialize distance tracking structures by assigning zero to the source vertex and infinity to all unvisited vertices.
• Execute edge relaxation conditionally to update adjacent vertex costs when shorter paths are discovered.
• Select the unvisited vertex with the minimum tentative distance using a greedy strategy at each iteration.
• Trace algorithm state transitions across directed graphs until all reachable vertices are permanently settled.
• Differentiate single-source shortest path objectives from minimum spanning tree algorithms like Prim's and Kruskal's.

Detailed Concept Walkthrough

1. Graph Setup and Distance Initialization

Dijkstra's algorithm computes the shortest path from a single source node to all other vertices by maintaining a tentative distance table. Setting unreachable nodes to infinity guarantees that any valid path found during traversal immediately overwrites the initial placeholder cost.

• Mechanism: You choose a designated source node, set its cumulative distance to zero, and set all other vertices to infinity in a dedicated tracking table. A set or boolean array tracks visited (settled) nodes to ensure each vertex is finalized only once.
• Under the Hood: Memory allocation requires $O(V)$ space for the distance lookup array and the visited tracking set. Using infinity ensures any incoming positive edge relaxation satisfies the inequality condition on first discovery.
• Best Practice: Always verify that edge weights are non-negative before initializing Dijkstra's algorithm, as negative edges invalidate greedy distance finalization.

# Initialize distances and visited tracking for graph vertices
def init_dijkstra(vertices, source):
    distances = {v: float('inf') for v in vertices}
    distances[source] = 0
    visited = set()
    return distances, visited

Key Takeaway: Initialization establishes the base state where only the source has a cost of zero while all other vertices remain infinitely far away.

2. Edge Relaxation Rule

Edge relaxation is the core operation that tests whether passing through a newly settled node offers a shorter path to a neighbor than previously recorded. If the candidate distance is strictly smaller, the neighbor's stored distance is updated.

• Mechanism: For an active node $u$ with known distance $dist[u]$, examine each outgoing edge $(u, v)$ with weight $w$. If $dist[u] + w < dist[v]$, overwrite $dist[v]$ with this new, smaller value.
• Under the Hood: Relaxation maintains the triangle inequality across graph paths, progressively tightening upper bounds toward exact shortest distances.
• Best Practice: Ensure strict inequality ($<$) during comparison to avoid redundant writes and unnecessary state pushes into the priority queue.

# Relax edge from u to v with edge weight w
def relax_edge(u, v, w, distances):
    new_dist = distances[u] + w
    if new_dist < distances[v]:
        distances[v] = new_dist
        return True  # Path updated
    return False

Key Takeaway: Relaxation updates a neighbor's tentative distance only when traversing the current node yields a strictly lower total cost.

3. Greedy Node Selection and Settling

At each step, the unvisited node with the smallest tentative distance is extracted and marked as settled. Because all edge weights are non-negative, no subsequent path through other unvisited nodes can ever reach this node with a smaller cost.

• Mechanism: Extract the minimum-distance vertex from the unvisited collection, mark it as closed, and relax all its outgoing edges to unvisited neighbors. Repeat this cycle until all reachable vertices are closed.
• Under the Hood: The greedy choice property guarantees optimal substructure; once a node with the lowest tentative distance is popped, its distance is finalized and frozen.
• Execution Flow: Start Node $\rightarrow$ Extract Min $\rightarrow$ Mark Visited $\rightarrow$ Relax Neighbors $\rightarrow$ Repeat until queue is exhausted.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    visited = set()
    
    while pq:
        curr_dist, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if v not in visited and curr_dist + weight < distances[v]:
                distances[v] = curr_dist + weight
                heapq.heappush(pq, (distances[v], v))
    return distances

Key Takeaway: Freezing the minimum tentative unvisited node guarantees shortest path finality under non-negative edge weight constraints.

4. Complexity Analysis and Data Structures

The overall time complexity of Dijkstra's algorithm depends directly on the data structure used to locate the minimum tentative distance node and update edge weights.

• Mechanism: Standard min-heaps achieve $O((V + E) \log V)$ time complexity by pushing updated distance-vertex pairs into a priority queue. Advanced Fibonacci heaps reduce decrease-key operations to amortized $O(1)$, yielding $O(E + V \log V)$.
• Under the Hood: An unoptimized linear scan over an array requires $O(V^2)$ time, which is acceptable for dense graphs ($E \approx V^2$) but inefficient for sparse graphs.
• Best Practice: In technical interviews, implement standard binary heaps (heapq in Python) and filter stale entries using a visited set.

# Graph represented as adjacency list: {node: [(neighbor, weight)]}
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8), ('E', 10)],
    'D': [('E', 2)],
    'E': []
}
# Running dijkstra(graph, 'A') yields shortest paths from 'A'

Key Takeaway: Using a min-priority queue optimizes sparse graph search time to $O((V + E) \log V)$ by streamlining minimum-distance extraction.

Topics Covered in Graph Algorithms (Dijkstra, Topological Sort)

1. Algorithm Foundation and Scope (0:00 - 0:13) — Dijkstra calculates single-source shortest paths on weighted graphs and differs from minimum spanning tree algorithms.
2. Graph Setup and Distance Initialization (0:14 - 0:33) — The source vertex is assigned a distance of zero while all other unvisited nodes are set to infinity.
3. Edge Relaxation and Node Selection (0:34 - 0:44) — Outgoing edges from the starting node are relaxed and the unvisited node with the lowest tentative cost is selected.
4. Iterative Path Optimization (0:46 - 1:09) — Visited nodes are closed and neighbor distances are iteratively relaxed to discover shorter intermediate paths.
5. Algorithm Termination (1:11 - 1:29) — The traversal concludes when all reachable nodes are settled and optimal distances are finalized in the table.
6. Complexity and Pseudocode Analysis (1:31 - 1:47) — Time complexity bounds are established based on heap data structures and formal pseudocode mechanics.

DSA for Interviews Cheat Sheet

• distances[source] = 0 — Initializes source distance to zero

  distances = {node: float('inf') for node in graph}; distances['A'] = 0
  

• heapq.heappush(pq, (dist, node)) — Pushes node and tentative distance to priority queue

  heapq.heappush(pq, (0, 'A'))
  

• curr_dist, u = heapq.heappop(pq) — Extracts unvisited node with minimum tentative distance

  curr_dist, u = heapq.heappop(pq)
  

• if new_dist < distances[v]: — Evaluates edge relaxation condition for neighbor node

  if distances[u] + weight < distances[v]: distances[v] = distances[u] + weight
  

• visited.add(u) — Marks node distance as permanently finalized

  visited.add(u)
  

Comparison Table

Common Pitfalls

• Mistake: Executing Dijkstra's algorithm on graphs with negative edge weights. Avoid: Use the Bellman-Ford algorithm whenever negative edge weights exist.
• Mistake: Overwriting neighbor distances when candidate paths have greater or equal cost. Avoid: Apply relaxation strictly when candidate distance is strictly less than current.
• Mistake: Re-relaxing edges from nodes that are already marked visited. Avoid: Skip already visited nodes immediately upon popping them from priority queue.

FAQs

• Why does Dijkstra's algorithm fail when negative edge weights are present? Dijkstra permanently freezes a node's distance once popped; negative edges can later produce a shorter path, violating the greedy assumption.
• How does Dijkstra differ fundamentally from Prim's or Kruskal's algorithms? Dijkstra minimizes cumulative distance from one start node, whereas Prim's and Kruskal's minimize the total edge weight connecting all vertices.
• Why do unvisited nodes start with a distance of infinity? Infinity represents unreachable state, allowing any real calculated edge cost to trigger the relaxation condition upon first discovery.
• What is the optimal time complexity using a standard binary heap versus a Fibonacci heap? Binary min-heaps run in $O((V + E) \log V)$ time, whereas Fibonacci heaps achieve $O(E + V \log V)$ via $O(1)$ amortized decrease-key operations.

Topological Sort: Course Supplement

The existing graph-algorithm video covers Dijkstra's shortest-path algorithm. This companion adds topological ordering for directed acyclic graphs (DAGs); the algorithms solve different problems.

Kahn's algorithm

Compute each vertex's indegree, enqueue all zero-indegree vertices, and repeatedly remove one, append it to the order, and decrement the indegree of its outgoing neighbors. Enqueue a neighbor exactly when its indegree becomes zero. If the output contains fewer than V vertices, the graph has a directed cycle and no topological ordering exists.

from collections import deque

def topological_order(graph):
    nodes = set(graph)
    for neighbors in graph.values():
        nodes.update(neighbors)
    adjacency = {node: list(graph.get(node, [])) for node in nodes}
    indegree = {node: 0 for node in nodes}
    for node, neighbors in adjacency.items():
        for neighbor in neighbors:
            indegree[neighbor] = indegree.get(neighbor, 0) + 1

    ready = deque(node for node, degree in indegree.items() if degree == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)
    return order if len(order) == len(indegree) else None

The implementation normalizes sink-only vertices into a local adjacency copy and does not mutate the caller's graph. Time is O(V+E), space O(V). The result need not be unique; any order that places every edge's source before its destination is valid.

DFS alternative and use cases

DFS adds a node after visiting its outgoing neighbors. A three-color state (unseen, active, done) detects a back edge to an active node, which proves a cycle. Topological order applies to dependency scheduling, course prerequisites, and build ordering. Dijkstra requires weighted edges and nonnegative weights to compute shortest paths; topological sort does not calculate distances and works on DAG dependencies regardless of edge weights.